专注收集记录技术开发学习笔记、技术难点、解决方案
网站信息搜索 >> 请输入关键词:
您当前的位置: 首页 > C语言

红色部分如何理解?

发布时间:2011-06-28 10:20:19 文章来源:www.iduyao.cn 采编人员:星星草
红色部分怎么理解??
给你三个数X(1<=X<=10^100)、Y(1<=Y<=10^8)、Z(1<=Z<=10^4),你能计算出X^Y%Z的值吗?

Description
输入三个如上所描述的数X、Y、Z。多组输入。

Input
输出X^Y%Z的值。

Output
2 3 5
12345 2345 345
123456789123456789 19234321 2341
Sample Input
3
240
1825
#include<stdio.h>
#include<string.h>
int main()
{
void res(char str[],int y,int a);
char str[1000];
int y,z;
while(scanf("%s%d%d",str,&y,&z)!=EOF)
{
res(str,y,z);
}
return 0;
}
void res(char str[],int y,int z)
{
int len=strlen(str);
int Value=0,i;
i=0;
while(i<len)
{
while(Value<100000 && i<len)
{
Value=Value*10+str[i]-'0';
i++;
}
Value %= z;
}
int result=1;
while(y>0)
{
if(y%2!=0)
result=(result*Value)%z;
Value=(Value*Value)%z;
y /= 2;
}

printf("%d\n",result);
}
------解决思路----------------------
红色部分,其是是想求value的y次方除以z取余。
一步一步来思考:
第一步就是 result = result * value % z, 循环y次,就得出结果

但是这样做是不是还能再优化呢?答案是肯定的。我们先用递归的思路思考一下:
比如 已经得到 result = result * value %z
那么 如果y是2 的话 那利用上面的 result 就可以得到 result = result * result %z
如果y是 4的话,再利用上一步的result,可以得到result = result * result %z
如果y是8的话,继续利用上一步的result,可以得到:result = result * result %z
......

其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。
具体红色那样做对不对呢?我现在还不想给你结论!(其实我还没优化到那一步,不许揭穿我!)

------------------------
个人见解。



友情提示:
信息收集于互联网,如果您发现错误或造成侵权,请及时通知本站更正或删除,具体联系方式见页面底部联系我们,谢谢。

其他相似内容:

热门推荐: