posts - 33,  comments - 25,  trackbacks - 0
ZOJ 1489 解题报告

解决此题需掌握两个基本原理:
1.任何奇数都可以被2n-1整除,而偶数则不能.
2.将n1...nx全部相乘后对M取模恒等于n1...nx分别单独对M取模后相乘.
基于以上两个原理,代码如下:

 1#include <iostream>
 2using namespace std;
 3
 4int _tmain(int argc, _TCHAR* argv[])
 5{
 6    int n;
 7    while(cin >> n)
 8    {
 9        if((n & 0x1) == 0)
10            cout << "2^? mod " << n << " = 1" << endl;
11        else
12        {
13            int temp = 1;
14            int result = 1;
15            while(true)
16            {
17                temp *= 2;
18                temp %= n;
19                if(temp == 1)
20                    break;
21                ++result;
22            }
23            cout << "2^" << result << " mod " << n << " = 1" << endl;
24        }
25    }
26    return 0;
27}
28
29

 

posted on 2009-03-26 21:01 肖羽思 阅读(585) 评论(0)  编辑 收藏 引用 所属分类: ZOJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年3月>
日一二三四五六
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜