Submission #15796955

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200100,P=200003;
const double pi=acos(-1);
int n,a[N],f[P],p[P];
int len,rev[P*4];
struct com
{
	long double real,ima;
}g[P*4];
com operator+(com a,com b){return(com){a.real+b.real,a.ima+b.ima};}
com operator-(com a,com b){return(com){a.real-b.real,a.ima-b.ima};}
com operator*(com a,com b){return(com){a.real*b.real-a.ima*b.ima,a.real*b.ima+b.real*a.ima};}
inline void change(int len)
{
	for (int i=0;i<len;i++)
	{
		rev[i]=rev[i>>1]>>1;
		if (i&1) rev[i]|=len>>1;
	}
}
inline void fft(com y[],int len,int v)
{
	for (int i=0;i<len;i++) if (i<rev[i]) swap(y[i],y[rev[i]]);
	for (int i=2;i<=len;i<<=1)
	{
		com step=(com){cos(2.0*pi/i),sin(v*2.0*pi/i)};
		for (int j=0;j<len;j+=i)
		{
			com x=(com){1.0,0};
			for (int k=j;k<j+i/2;k++)
			{
				com a=y[k],b=x*y[k+i/2];
				y[k]=a+b,y[k+i/2]=a-b;
				x=x*step;
			}
		}
	}
	if (v==-1) for (int i=0;i<len;i++) y[i].real/=1.0*len;
}
signed main()
{
	scanf("%lld",&n);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	f[1]=0;
	int x=1;
	for (int i=1;i<P-1;i++) x=(x+x)%P,f[x]=i;
	p[0]=1;
	for (int i=1;i<P-1;i++) p[i]=(p[i-1]+p[i-1])%P;
	for (int i=1;i<=n;i++) if (a[i]!=0) g[f[a[i]]].real+=1;
	len=1;
	while (len<P+P) len<<=1;
	change(len);
	fft(g,len,1);
	for (int i=0;i<len;i++) g[i]=g[i]*g[i];
	fft(g,len,-1);
	for (int i=1;i<=n;i++) if (a[i]!=0) g[f[a[i]]*2].real-=1;
	int ans=0;
	for (int i=0;i<len;i++) ans+=p[i%(P-1)]*((int)(g[i].real+0.5)/2);
	printf("%lld\n",ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:44:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
./Main.cpp:45:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   45 |  for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
      |                         ~~~~~^~~~~~~~~~~~~~

Judge Result