红色部分如何理解?
发布时间: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
......
其实红色的部分就是要把上述的递归部分转化成循环的方法来实现。
具体红色那样做对不对呢?我现在还不想给你结论!(其实我还没优化到那一步,不许揭穿我!)
------------------------
个人见解。
友情提示:
信息收集于互联网,如果您发现错误或造成侵权,请及时通知本站更正或删除,具体联系方式见页面底部联系我们,谢谢。
其他相似内容:
-
【★C/C++奖励基金-30期★】更新获奖书籍,请选择~ - C/C++ / 非技术区
【★C/C++奖励基金-30期★】
C/C++ 2011-12专家榜
名次...
-
C/c++ 如何按位拷贝呢?
我有一个结构体
strut st_header
{
unsigned short ver:2
unsigned short ping:1
unsgne...
-
uboot上的一点代码,没看明白!
struct in_str {
const char *p;
#ifndef __U_BOOT__
char peek_buf[2];
#endif
int __promptme;
...
-
Debug时为什么变量的地址不变?
是巧合还是某种必然. 是不是因为C中生成的可执行程序存储的地址是相对地址而不是绝对的物理地址.
...
-
关于switch语句。我不知道哪里错了,大侠帮忙bug一下
#include <stdio.h>
int main()
{
int a;
char b;
do{
printf("1.Chines...
-
#pragma section 的 $ 语法
在 ARX 头文件中间过如下三行,放在一起:
#pragma section("ARXCOMMAND$__a")
#pragma section("ARXCOMM...
-
read 问题再现
#define N 205
signed short x[N];
for(i=0;i<N;i++)
{
printf("hello boy!!\n");
...
-
征求一个C语言输入函数?
不知道大家有没有学习过Java? 现在需要一个类似Java的Scanner的函数集, 要求如下:
1. 三个函数: int rea...
-
求一道算法。一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?
/*我写了一点,但是有错误,汗*/
/*
...
-
3n+1问题
求救,不知道错在哪里
#include<stdio.h>
int count(int a,int b)
{
int max=0,len=0,a1;
while(a<=b)
{
...