hdu-1395 2^x mod n = 1---求阶（欧拉函数）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1395

题目大意：

题目中给出输入一个整数n，要求一个最小整数的x，使得2^x mod n=1;

解题思路：

2^x = 1（mod n）就是求2模上n的阶。

传送门：阶与原根

如果n是偶数或者是1，答案一定不存在

如果是偶数，2^x也是偶数，偶数模上偶数不可能为1。

如果n为1，那么模的结果一定为0。

如果n是奇数，那么可以求阶，也可以暴力（数据水）

求阶的方法：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int a[];

 int euler_phi(int n)//求单个

 {

     int m = (int)sqrt(n + 0.5);

     int ans = n;

     for(int i = ; i <= m; i++)if(n % i == )

     {

         ans = ans / i * (i - );

         while(n % i == )n /= i;

     }

     if(n > )ans = ans / n * (n - );

     return ans;

 }

 ll pow(ll a, ll b, ll m)

 {

     a %= m;

     ll ans = ;

     while(b)

     {

         if(b & )ans = ans * a % m;

         a = a * a % m;

         b /= ;

     }

     return ans % m;

 }

 int main()

 {

     int n;

     while(cin >> n)

     {

         int tot = ;

         if(n %  ==  || n == )

         {

             printf("2^? mod %d = 1\n", n);

             continue;

         }

         int t = euler_phi(n);

         //cout<<t<<endl;

         for(int i = ; i * i <= t; i++)

         {

             if(t % i == )

             {

                 a[tot++] = i;

                 if(i * i != t)a[tot++] = t / i;

             }

         }

         sort(a, a + tot);

         //for(int i = 0; i < tot; i++)printf("%d ", a[i]);

         for(int i = ; i < tot; i++)

         {

             if(pow(, a[i], n) == )

             {

                 printf("2^%d mod %d = 1\n", a[i], n);

                 break;

             }

         }

     }

     return ;

 }

巴特西

hdu-1395 2^x mod n = 1---求阶（欧拉函数）

最新文章

热门文章