2^x mod n = 1题解

goodmarket · 2018-12-02 22:46:28 · 个人记录

题目链接:[https://cn.vjudge.net/problem/HDU-1395]()

题意:找到满足2^x mod n = 1 的最小n。

思路:可以知道当n为偶数与1时余数最后一位为偶数不为0所以无法找到满足条件的值。当n为奇数时有解,于是每次将所得数反复乘以2再去余即可。

代码:

#include<iostream>
#include<cmath>
using namespace std;
int n;
int main()
{
    int leave=1,temp=0;
    while(cin>>n)
    {  
        if(n%2==0||n==1)
        {
            cout<<"2^? mod "<<n<<" = 1"<<endl;
        }
        else
        {
            int i;
            for(i=1;;i++)
            {
                leave=leave*2%n;
                if(leave==1)
                break;
            }
            cout<<"2^"<<i<<" mod "<<n<<" = 1"<<endl;
        }
        leave=1;
    }   
    return 0;
}