首页 > 代码库 > 2011的n次方
2011的n次方
题目:http://noi.openjudge.cn/ch0204/2991/
- 总时间限制:1000ms 内存限制: 65536kB
- 描述
- 已知长度最大为200位的正整数n,请求出2011^n的后四位。
- 输入
- 第一行为一个正整数k,代表有k组数据,k<=200接下来的k行,
每行都有一个正整数n,n的位数<=200 - 输出
- 每一个n的结果为一个整数占一行,若不足4位,去除高位多余的0
- 样例输入
-
3 5 28 792
- 样例输出
-
1051 81 5521
参考:
利用循环节:http://m.blog.csdn.net/u013675643/article/details/51820648
高精度除法:http://blog.csdn.net/qq_35479641/article/details/51810945
下面的思路参照循环节的做法。
题目只需要输出后四位,因此答案必然有一个最多5位数的循环节。于是可以先写个暴力去找循环节,发现循环节长度为500,这个数就很好处理了。后面读入n时只保留后三位数,再mod500就得出答案了,比写高精度简单多了~
1 #include<stdio.h> 2 #include<string.h> 3 // m^n % k 4 long long quickpow(long long m,long long n,long long k) 5 { 6 long long ans = 1; 7 while (n > 0) 8 { 9 if (n & 1) 10 ans = (ans*m)%k; 11 n = n >> 1 ; 12 m = (m*m)%k; 13 } 14 return ans; 15 } 16 int main(int argc, char *argv[]) 17 { 18 int k; 19 int i; 20 char n[205]; 21 int N,len; 22 scanf("%d",&k); 23 for(i=0;i<k;i++) 24 { 25 scanf("%s",n);getchar(); 26 N=0; 27 len=strlen(n); 28 N=n[len-1]-‘0‘; 29 if(len>=2) N=(n[len-2]-‘0‘)*10+N; 30 if(len>=3) N=(n[len-3]-‘0‘)*100+N; 31 if(len>=4) N=(n[len-4]-‘0‘)*1000+N; 32 N=N%500; 33 printf("%lld\n",quickpow(2011,N,10000)); 34 } 35 return 0; 36 }
还有一个数学论证:http://blog.csdn.net/li744831579/article/details/8784547
2011的n次方
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。