红色部分怎么理解？？

c语言给你三个数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=Value10+str[i]-“”0″”; i++; } Value %= z; } int result=1; while(y>0) { if(y%2!=0) result=(resultValue)%z; Value=(Value*Value)%z; y /= 2; } printf(“%d\n”,result); }
	x^y = x^(y/2) y为偶数 x^y = x * x^(y/2) y为奇数
40分	红色部分，其是是想求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 …… 其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。具体红色那样做对不对呢？我现在还不想给你结论！（其实我还没优化到那一步，不许揭穿我！） ———————— 个人见解。
	引用 2 楼 henuyx 的回复: 红色部分，其是是想求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 …… 其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。具体红色那样做对不对呢？我现在还不想给你结论！（其实我还没优化到那一步，不许揭穿我！） ———————— 个人见解。说得有道理. 其实就跟2进制一样,从低位到高位这样跌起来.有1就加起来.
	把%z去掉就是快速冪的算法，
	引用 2 楼 henuyx 的回复: 红色部分，其是是想求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 …… 其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。具体红色那样做对不对呢？我现在还不想给你结论！（其实我还没优化到那一步，不许揭穿我！） ———————— 个人见解。 2楼的朋友，，谢了哈，懂了一些，，，红色那里是对的

c语言给你三个数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=Value10+str[i]-“”0″”; i++; } Value %= z; } int result=1; while(y>0) { if(y%2!=0) result=(resultValue)%z; Value=(Value*Value)%z; y /= 2; } printf(“%d\n”,result); }
	x^y = x^(y/2) y为偶数 x^y = x * x^(y/2) y为奇数
40分	红色部分，其是是想求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 …… 其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。具体红色那样做对不对呢？我现在还不想给你结论！（其实我还没优化到那一步，不许揭穿我！） ———————— 个人见解。
	引用 2 楼 henuyx 的回复: 红色部分，其是是想求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 …… 其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。具体红色那样做对不对呢？我现在还不想给你结论！（其实我还没优化到那一步，不许揭穿我！） ———————— 个人见解。说得有道理. 其实就跟2进制一样,从低位到高位这样跌起来.有1就加起来.
	把%z去掉就是快速冪的算法，
	引用 2 楼 henuyx 的回复: 红色部分，其是是想求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 …… 其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。具体红色那样做对不对呢？我现在还不想给你结论！（其实我还没优化到那一步，不许揭穿我！） ———————— 个人见解。 2楼的朋友，，谢了哈，懂了一些，，，红色那里是对的

文章评论已关闭！