凝升

用户名：ningsheng

访问量：4111

签　名：

等　　级
排　　名	2957
经　　验	1992
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	sdu
专　　业

　　自我简介：

TA的其他文章

剔除相关数-题解(C++代码)
浏览：502

化学品问题-题解(C++代码)
浏览：676

你可能喜欢

循环-题解(C++代码)

　　作者: 凝升　　　　发表时间：2019-08-10 23:56:09 浏览：2095　|　评论：1　

原题链接：循环

**问题分析**
----
**这是一道高精度幂的题**
**除了简单高精度幂还要考虑时间复杂度的优化，题面上写着n的数量级是10的4次方，k的数量级是100，直接累乘最后会超时**

**循环节优化**
----
**这个优化用一句话概括：后k位的循环节是后k-1位循环节的倍数**
[![](http://s2.sinaimg.cn/orignal/61125321g6e8ce234ed91&690)](http://s2.sinaimg.cn/orignal/61125321g6e8ce234ed91&690)

[[1]][证明]
[证明]: http://blog.sina.com.cn/s/blog_611253210100dv77.html "第十一届NOIP(2005)普及组复赛第4题(循环)分析(C++)"

**思路**
----
**有了循环节优化后，我们可以详细考虑一下怎么高效的实现这个算法，我们先求出后k-1位的循环节，且将这时候的累乘结果保存下来，然后再求后k位的循环节，因为每一位能出现的只有数字0-9，所以如果后k-1位的循环节在其1-9倍里都不是后k位的循环节，此时就不存在答案了，直接输出-1，退出程序。也正是因为这种依次求出前一位的循环节的方法，我们可以每次只检测要求的那一位是否匹配**

**为了便于计算，我们可以只记录累乘结果中的后k位，因为后k位乘积只跟后k位的数值有关**

**这道题的细节点**
----
**1. 题面上的n的范围不是那么简单，使用int去记录会WA一部分数据**
**2. 最后的结果，也就是循环节的值，建议也使用数组去记录，不然也会出现WA的结果**
**3. 注意及时对累乘的结果数组和乘数进行更新**

**带详细注释的代码**
----
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    int k;
    
    void mul(int* a,int b,int* c){//高精低乘
    	for(int i=0;i<=k;i++)c[i]=0;
    	int cou=0;
    	for(int i=1;i<=k;i++){
    		c[i]=a[i]*b+cou;
    		cou=c[i]/10;
    		c[i]%=10;
    	}
    }
    
    void mult(int *a,int* b,int* c){//高精高乘
    	for(int i=0;i<=k;i++)c[i]=0;
    	for(int i=1;i<=k;i++)
    		for(int j=1;i+j-1<=k;j++)
    			c[j+i-1]+=a[j]*b[i];
    	int cou=0;int go=0;
    	for(int i=1;i<=k;i++){
    		go=c[i]+cou;
    		c[i]=go%10;
    		cou=go/10;
    	}
    }
    
    int main(){
    	string s;
    	cin>>s>>k;//读入数据，建议用string类型读入，使用int会WA
    
    	//将字符串转换成整型数组存储
    	int ss=s.size();
    	int n[ss+1],//存储n
    		n0[k+1],//只取n的后k位，该数组用于比较进行每一位的循环匹配
    		c0[k+1],//每次累乘的结果
    		c1[k+1],//每次累乘的乘数一
    		c2[k+1],//每次累乘的乘数二
    		c3[k+1];//n的循环节次幂再乘以n存放于该数组再与n0进行匹配，即c3=c0*n
    
    	//将字符串转换成整型数组，注意顺序颠倒
    	for(int i=0;i<ss;i++)
    		n[ss-i]=s[i]-'0';
    	//对数组进行初始化
    	for(int i=1;i<=k;i++)
    		if(i<=ss)
    			c2[i]=c1[i]=c0[i]=n0[i]=n[i];
    		else
    			c2[i]=c1[i]=c0[i]=n0[i]=0;
    
    	//存储循环节的数组nowc，其nowcc是辅助数组
    	int nowc[101],nowcc[101];
    	memset(nowc,0,sizeof(nowc));
    	memset(nowcc,0,sizeof(nowcc));
    	nowc[1]=nowcc[1]=1;
    
    	for(int i=1;i<=k;i++){
    		for(int j=1;j<=11;j++){
    			mult(c0,n,c3);//n的已计算出的循环节次幂存储在c0，再乘以n得到要匹配的值
    			if(c3[i]==n0[i]){
    				mul(nowc,j,nowcc);//更行循环节
    				copy(nowcc,nowcc+101,nowc);
    				copy(c0,c0+k+1,c2);//更新乘数二
    				break;
    			}
    			else if(j==11){//没有循环节
    				cout<<-1<<endl;
    				return 0;
    			}
    			//累乘
    			mult(c1,c2,c0);
    			copy(c0,c0+k+1,c1);
    		}
    	}
    	//去除前导0，输出答案
    	int ii;
    	for(ii=100;ii>=1&&nowc[ii]==0;ii--);
    	while(ii>0)
    		cout<<nowcc[ii--];
    	return 0;
    }

------------

**这道题也卡了我很久，答案错误在64%，73%，82%，91%，这些错误的原因都在上面的细节点里，注意好了就AC了，加油**

**现在的你是最菜的自己，但未来的你可以无可匹敌**

0.0分

17 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

dotcpp0693251

额，输入9和2的时候应该是10，博主答案错的呢

2023-11-19 12:56:00

凝升

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

模拟计算器（Java代码）

不需要数组和指针的做法！！！

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

计算质因子（C++代码）100以内质数直接打表就好了

循环-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言训练-舍罕王的失算（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

Wu-求圆的面积（C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

凝升

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

模拟计算器 （Java代码）

不需要数组和指针的做法！！！

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

计算质因子 （C++代码）100以内质数直接打表就好了

循环-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言训练-舍罕王的失算 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

Wu-求圆的面积 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

模拟计算器（Java代码）

计算质因子（C++代码）100以内质数直接打表就好了

　　评论区

C语言训练-舍罕王的失算（C语言代码）

九宫重排（C++代码）

Wu-求圆的面积（C++代码）