Problem about GCD
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 470 Accepted Submission(s):
77
Problem Description
Given integer m. Find multiplication of all
1<=a<=m such gcd(a, m)=1 (coprime with m) modulo m.
1<=a<=m such gcd(a, m)=1 (coprime with m) modulo m.
Input
Input contains multiple tests, one test per
line.
Last line contains -1, it should be skipped.
line.
Last line contains -1, it should be skipped.
[Technical
Specification]
m <= 10^18
Output
For each test please output result. One case per line.
Less than 160 test cases.
Less than 160 test cases.
Sample Input
1
2
3
4
5
-1
Sample Output
1
2
3
4
Source
打表找规律：
数字n 如果由 x^k组成 或者 2*y^k 组成（x,y不等于2了，k为1,2,3,....） 则结果为n-1；
否则为1.
思路:
1.特判%4的情况。
2.m = n , 如果m为偶数先除2 。
3.如果m本身就是素数 m = m^1 ,那就是n-1了。
4.如果m由两个素数组成 m = x*x ,x是素数. 也简单，开平方，然后判断是不是素数。
5.如果m由多个素数组成 m = x^k,那么这个素数一定在10^6里面出现。
至少为3次吧。
代码很挫。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<stdlib.h>
#include<time.h>
#include<math.h>
using namespace std;
typedef __int64 LL;
const int maxn = 1e6+;
int prime[maxn],len;
bool s[maxn]; void init()
{
int i,j;
len = ;
memset(s,true,sizeof(s));
s[] = false;
for(i=;i<maxn;i++)
{
if(s[i] == false) continue;
prime[++len] = i;
for(j=i*;j<maxn;j=j+i)
s[j] = false;
}
}
//****************************************************************
// Miller_Rabin 算法进行素数测试
//速度快，而且可以判断 <2^63的数
//****************************************************************
const int S=;//随机算法判定次数，S越大，判错概率越小
LL mult_mod(LL a,LL b,LL mod) //(a*b)%c a,b,c<2^63
{
a%=mod;
b%=mod;
LL ans=;
while(b)
{
if(b&)
{
ans=ans+a;
if(ans>=mod)
ans=ans-mod;
}
a=a<<;
if(a>=mod) a=a-mod;
b=b>>;
}
return ans;
}
LL pow_mod(LL a,LL b,LL mod) // a^b%mod
{
LL ans=;
a=a%mod;
while(b)
{
if(b&)
{
ans=mult_mod(ans,a,mod);
}
a=mult_mod(a,a,mod);
b=b>>;
}
return ans;
} //以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数
//一定是合数返回true,不一定返回false bool check(LL a,LL n,LL x,LL t)
{
LL ret=pow_mod(a,x,n);
LL last=ret;
for(int i=;i<=t;i++)
{
ret=mult_mod(ret,ret,n);
if(ret== && last!= && last!=n-) return true;//合数
last=ret;
}
if(ret!=) return true;
else return false;
} // Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false; bool Miller_Rabin(LL n)
{
if(n<)return false;
if(n==) return true;
if( (n&)==) return false;//偶数
LL x=n-;
LL t=;
while( (x&)== ) { x>>=;t++;}
for(int i=;i<S;i++)
{
LL a=rand()%(n-)+;//rand()需要stdlib.h头文件
if(check(a,n,x,t))
return false;//合数
}
return true;
}
bool Euler(LL n)
{
LL i , knum = ;
for(i=;prime[i]<=n&&i<=len;i++)
{
if(n%prime[i]==)
{
while(n%prime[i]==)
n=n/prime[i];
knum++;
}
if(knum>=) break;
}
if(knum == && n==) return true;
/**此处为n == 1 不是n == 0**/
return false;
}
void solve(LL n,LL m)
{
if( (m<= && s[m] == true) || Miller_Rabin(m) == true)
{
printf("%I64d\n",n-);
return;
}
LL k = (LL)sqrt(m*1.0);
if(k * k == m && Miller_Rabin(k) == true)
{
printf("%I64d\n",n-);
return;
}
if(Euler(m)==true)
{
printf("%I64d\n",n-);
return;
}
printf("1\n");
}
int main()
{
init();
LL n , m;
while(scanf("%I64d",&n)>)
{
if(n==-) break;
if(n<=){
printf("%I64d\n",n-);
continue;
}
m = n;
if( (m&) == )
{
m = m /;
if((m&)==)
{
printf("1\n");
continue;
}
}
solve(n,m);
}
return ;
}