初涉数论
题目描述
对于给定的 x , 求出使得 x^y%mod = 1 的最小正整数y ， 其中 mod = 790660457 .
输入
多组输入(最多50000组 )
每组一个x ( 0 < x < mod )
输出
首先测试组数 , 然后输出对应的最小正整数 y , 具体见样例
样例输入
1
3
样例输出
Case #1: 1
Case #2: 790660456 提示
费马小定理 快速幂
一个由费马小定理推出来的结论，这个y一定会是mod-1的因子。
//Asimple #include <bits/stdc++.h> #define INF 0xfffffff #define mod 790660457 #define swap(a,b,t) t = a, a = b, b = t #define CLS(a, v) memset(a, v, sizeof(a)) #define debug(a) cout << #a << " = " << a <<endl #define abs(x) x<0?-x:x #define srd(a) scanf("%d", &a) #define src(a) scanf("%c", &a) #define srs(a) scanf("%s", a) #define srdd(a,b) scanf("%d %d",&a, &b) #define srddd(a,b,c) scanf("%d %d %d",&a, &b, &c) #define prd(a) printf("%d\n", a) #define prdd(a,b) printf("%d %d\n",a, b) #define prs(a) printf("%s\n", a) #define prc(a) printf("%c", a) using namespace std; typedef long long ll; const int maxn = 1001; int n, m, num, T, k, len, ans, sum; int dp[maxn];
//找因子
void solve() { len = 0; ll num = mod-1; for(int i=1; i*i<=num; i++) { if( num % i == 0 ) { dp[len++] = i; if( num/i!=i ) { dp[len++] = num/i; } } } sort(dp, dp+len); } //快速幂 ll qpow(ll a, ll b, ll md) { ll ans = 1; while( b ) { if( b & 1 ) ans = ans * a % md; a = a * a % md; b = b >> 1; } return ans; } void input() { int ci = 0; solve(); while( ~srd(n) ) { printf("Case #%d: ", ++ci); for(int i=0; i<len; i++) { if( qpow(n, dp[i], mod) == 1 ) { prd(dp[i]); break; } } } } int main(){ input(); return 0; }
