首页 > 代码库 > 简单数论问题
简单数论问题
简单数论问题
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 15 Accepted Submission(s) : 5
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Given two positive integers a and N, satisfaing gcd(a,N)=1, please find the smallest positive integer x with a^x≡1(mod N).
Input
First is an integer T, indicating the number of test cases. T<3001.
Each of following T lines contains two positive integer a and N, separated by a space. a<N<=1000000.
Each of following T lines contains two positive integer a and N, separated by a space. a<N<=1000000.
Output
For each test case print one line containing the value of x.
Sample Input
22 33 5
Sample Output
24
Author
HYNU
// 题意：求满足a^x mod n恒等于1 的最小x值。
// 背景： 对任何两个互质的正整数a, m, m>=2有
a^φ(m)≡1(mod m) φ(m）即为m的欧拉函数
即欧拉定理
当m是质数p时，此式则为：
a^(p-1)≡1(mod m) 表示如果m是质数那么m的欧拉函数即是m-1。
即费马小定理。
// 题解：先打表出1-N的欧拉函数值然后枚举欧拉函数进行质因数分解，不断更新最小值。
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>using namespace std;const int Max = 1000010;int prime[Max], phi[Max]; //保存所有值的欧拉函数void fun() //求1到max所有值的欧拉函数{ prime[0] = prime[1] = 0; for(int i = 2;i <= Max; i ++) prime[i]=1; for(int i = 2; i*i <= Max; i ++) if(prime[i]) for(int j=i*i;j<=Max;j+=i) prime[j]=0; for(int i=1;i<=Max;i++) phi[i]=i; for(int i=2;i<=Max;i++) if(prime[i]) for(int j = i; j <= Max; j += i) phi[j] = phi[j]/i * (i-1);}int Mod(int a, int b, int c) //快速幂取模 { int ans = 1; long long aa = a; while(b) { if (b % 2) ans = ans * aa % c; aa = aa * aa % c; b /= 2; } return ans;}int main(){// freopen("a.txt","r",stdin);// freopen("b.txt","w",stdout); fun(); int t, a, n; cin >> t; while(t --) { cin >> a >> n; int sn = (int)sqrt(phi[n]), ans = n; //在1-sn之间枚举n的欧拉函数的因子 for(int i = 1; i <= sn; i++) //在欧拉函数的所有因子中查找满足条件并且是最小的。 { if (phi[n] % i == 0) //如果i是phi的因子 更新最小值 { if (Mod(a, i, n) == 1 && ans > i) ans = i; if (Mod(a, phi[n] / i, n) == 1 && ans > phi[n] / i) ans = phi[n] / i; } } cout << ans << endl; } return 0;}简单数论问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。