网站建设有哪些软件有哪些,wordpress怎么pjax,青岛网站的优化,wordpress 4.7 教程题目描述
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天#xff0c;他突然对数的正整数次幂产生了兴趣。
众所周知#xff0c;22 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6…2,4,8,6,2,4,8,6… 我们说 22 的正整数次幂最后一位的循环长度…题目描述
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天他突然对数的正整数次幂产生了兴趣。
众所周知22 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6…2,4,8,6,2,4,8,6… 我们说 22 的正整数次幂最后一位的循环长度是 44实际上 44 的倍数都可以说是循环长度但我们只考虑最小的循环长度。类似的其余的数字的正整数次幂最后一位数也有类似的循环现象
数字循环循环长度22,4,8,6433,9,7,1444,6255166177,9,3,1488,4,2,6499,12数字23456789循环2,4,8,63,9,7,14,6567,9,3,18,4,2,69,1循环长度44211442
这时乐乐的问题就出来了是不是只有最后一位才有这样的循环呢对于一个整数 n 的正整数次幂来说它的后k位是否会发生循环如果循环的话循环长度是多少呢
注意
如果 n 的某个正整数次幂的位数不足 k那么不足的高位看做是 00。如果循环长度是 L那么说明对于任意的正整数 an 的 a 次幂和 aL 次幂的最后 k 位都相同。
输入格式
共一行包含 22 个整数 n 和 k。n 和 k 之间用一个空格隔开表示要求 n 的正整数次幂的最后 k 位的循环长度。
输出格式
一个整数表示循环长度。如果循环不存在输出 −1−1。
输入输出样例
输入 #1复制
32 2
输出 #1复制
4
说明/提示
【数据范围】
对于 30%30% 的数据满足 ≤4k≤4 对于100%100% 的数据满足 1≤101001≤n101001≤≤1001≤k≤100。
【题目来源】
NOIP 2005 普及组第四题
题意
给定两整数 ,n,k求 n 的正整数次幂的最后 k 位的循环长度若循环不存在输出 −1−1。
1≤≤10100,1≤≤1001≤n≤10100,1≤k≤100
题解
这篇题解是对最高赞题解的补充与说明
在看最高赞题解的时候因为没有放上计算过程我对着题解手玩了好久才弄明白所以就有了这篇附上计算过程的题解。
手玩数据 198123 4因为要求只取后 4 位所以将其截取成 8123。
我们逐位进行处理
先处理最后一位的循环节最后一位是 3循环节长度为 4。所以后两位的循环节长度一定为 4 的倍数为了加快计算我们可以将乘数变为 8123^4 取后 4 位变成 0641。再处理后两位后两位是 23 在乘了 5 次 0641 后出现了循环循环节长度为 4*520。同样为了加快计算乘数变为 8123^200641^5取后 4 位变成 9201。之后就按照这样的方法处理即可。后三位后三位是 123 乘了 5 次 9201 后出现循环循环节长度为 20*5100 乘数变为 9201^5%(10^4)6001后四位后四位是 8123 乘了 5 次 6001 后出现循环循环节长度为 100*5500500 就是最终的答案。
记得判断无解的情况如果在处理某一位时乘了乘数 10 次还是没有出现循环无解。
8123 1
8123*812365983129 2
3129*812325416867 3
6867*812355780641 4
0641*812305206843 #
8123^443537733126306418123 1
8123*064105206843 2
6843*064104386363 3
6363*064104078683 4
8683*064105565803 5
5803*064103719723 #
0641^51082156687392018123 1
8123*920174739723 2
9723*920189461323 3
1323*920112172923 4
2923*920126894523 5
4523*920141616123 #
9201^5659439797557264460018123 1
8123*600148746123 2
6123*600136744123 3
4123*600124742123 4
2123*600112740123 5
0123*600100738123 #ans4*5*5*5500代码
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int k;
char str[205];
struct bignum
{int x[205];bignum(){memset(x,0,sizeof(x));}
}n,tmp,mul,ans;
bignum operator *(bignum a,bignum b)//特化过的高精乘 只取后k位
{bignum ans;for(int i0;ik;i)for(int j0;jk;j)ans.x[ij]a.x[i]*b.x[j];for(int i0;ik;i)ans.x[i1]ans.x[i]/10,ans.x[i]%10;for(int ik;i205;i)ans.x[i]0;return ans;
}
bignum operator *(bignum a,int b)//这个高精乘低精是ans专用的233
{for(int i0;i200;i)a.x[i]*b;for(int i0;i200;i)a.x[i1]a.x[i]/10,a.x[i]%10;return a;
}
int main()
{scanf(%s %d,str,k);ans.x[0]1;int lenstrlen(str);for(int i0;ik;i)n.x[i]str[len-i-1]-0;muln;for(int i0;ik;i){bignum tmpn;int j1,flag1;for(j1;j10;j){tmptmp*mul;if(tmp.x[i]n.x[i]){ansans*j;flag0;break;}}if(flag)return puts(-1),0;tmpmul;for(int k1;kj;k)mulmul*tmp;}len200;while(ans.x[len]0len1)len--;for(;len0;len--)putchar(ans.x[len]0);
}
