Submission #2092456

---

Source Code Expand

#include<cstdio>
#define int long long
inline int sqr(int a,int m){return a*a%m;}
int pow(int a,int n,int m)
{
	if(!n)return 1;
	if(n&1)return sqr(pow(a,n>>1,m),m)*a%m;
	return sqr(pow(a,n>>1,m),m);
}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void gcd(int x,int y,int &a,int &b)
{
	if(!y){a=1;b=0;return;}
	gcd(y,x%y,b,a);b-=x/y*a;
}
int solve(int a,int m)
{
	if(m==1)return 1;
	int phi=m,k=m;
	for(int i=2;i*i<=m;i++)
		if(k%i==0)
		{
			phi=phi/i*(i-1);
			while(k%i==0)k/=i;
		}
	if(k>1)phi=phi/k*(k-1);
	int g=gcd(m,phi),y=solve(a,g),o=(pow(a,y,m)-y+m)%m,p,q;
	if(y==-1||o%g)return -1;
	gcd(phi,m,p,q);
	p=(p+m)*o/g%m;
	return y+phi*p;
}
int q,a,m;
signed main()
{
	scanf("%lld",&q);
	while(q--)
	{
		scanf("%lld%lld",&a,&m);
		printf("%lld\n",solve(a,m));
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:36:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&q);
                  ^
./Main.cpp:39:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a,&m);
                          ^

Judge Result