[数学题]zju_1489
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
#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;
}
}
}
为什么取ＭＯＤ后再乘后再ＭＯＤ跟一直乘后再取ＭＯＤ是等效的呢？模运算还有没有其它的公式或定理，能贴上来一起分享吗？ 你列几个出来就会发现商是没有用的
只要余数一直乘就可以了 但为什么可以的？？？我知道是这样啊！但我想知道为什么是这样啊？ a1*a2*a3....anMODn=(a1MODn*a2MODn*a3MODn......)MODn 问啊老大吧 其实只要把数制转换成 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决定
页:
[1]