[数学题]zju_1489

sheep426

2^x mod n = 1

--------------------------------------------------------------------------------

Time limit: 1 Seconds   Memory limit: 32768K   
Total Submit: 7722   Accepted Submit: 1853   

--------------------------------------------------------------------------------

Give a number n, find the minimum x that satisfies 2^x mod n = 1.


Input

One positive integer on each line, the value of n.


Output

If the minimum x exists, print a line with 2^x mod n = 1.

Print 2^? mod n = 1 otherwise.

You should replace x and n with specific numbers.


Sample Input

2
5


Sample Output

2^? mod 2 = 1
2^4 mod 5 = 1


Author: MA, Xiao

sheep426

#include <iostream>

using namespace std;

int main()
{
        long n,weight,a;
        while(cin >> n)
        {
                if(n % 2 == 0 || n<=2 )
                {
                         cout<<\"2^? mod \"<<n<<\" = 1\"<<endl;
                }
                else
                {
                        weight = 1;
                        a = 2;
                        while( a % n != 1)
                        {
                                a = (a % n)*2;
                                weight++;
                        }
                        cout<<\"2^\"<<weight<<\" mod \"<<n<<\" = 1\"<<endl;
                }
        }
}

剑乱

为什么取ＭＯＤ后再乘后再ＭＯＤ跟一直乘后再取ＭＯＤ是等效的呢？模运算还有没有其它的公式或定理，能贴上来一起分享吗？

sheep426

你列几个出来就会发现商是没有用的
只要余数一直乘就可以了

剑乱

但为什么可以的？？？我知道是这样啊！但我想知道为什么是这样啊？

剑乱

a1*a2*a3....anMODn=(a1MODn*a2MODn*a3MODn......)MODn

小康

问啊老大吧

leol

其实只要把数制转换成 n 进制看就可以知道原因了
譬如 x = a0*n^0+a1*n^1+a2*n^2+...+ai*n^i
那么,a1*n^1+a2*n^2+...+ai*n^i显然是 mod n == 0的,余数实质上只由a0决定