URAL 1268. Little Chu最大の元のルートを求めます
1203 ワード
标题名称:URAL 1268.Little Chu
标题:nを入力して最大のkを求めてk^1 k^2 k^3...k^x mod n以降はそれぞれ異なります
考え方:mod nの後でそれぞれ異なって最大でn個ありますそれではこの事kは元の根ですk<=nだからnから下に1つの最大の元の根を列挙して求めます
标题:nを入力して最大のkを求めてk^1 k^2 k^3...k^x mod n以降はそれぞれ異なります
考え方:mod nの後でそれぞれ異なって最大でn個ありますそれではこの事kは元の根ですk<=nだからnから下に1つの最大の元の根を列挙して求めます
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
int p[100000], c;
LL pow_mod(LL a, LL x, LL m)
{
LL ans = 1;
while(x)
{
if(x&1)
ans = ans * a % m;
a = a * a % m;
x >>= 1;
}
return ans;
}
bool ok(int x, int ph, int m)
{
for(int i = 0; i < c; i++)
if(pow_mod(x, ph/p[i], m) == 1)
return false;
return true;
}
void divide(int x)
{
c = 0;
for(int i = 2; i*i <= x; i++)
{
if(x % i == 0)
{
p[c++] = i;
while(x % i == 0)
x /= i;
}
}
if(x > 1)
p[c++] = x;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int n;
scanf("%d", &n);
int m = n, ans = m;
for(int i = 2; i*i <= n; i++)
{
if(n%i == 0)
{
ans = ans / i * (i-1);
while(n%i == 0)
n /= i;
}
}
if(n > 1)
ans = ans / n * (n-1);
//printf("%d
", ans);
divide(ans);
int x = ans;
while(!ok(x, ans, m))
x--;
printf("%d
", x);
}
return 0;
}