凝升

用户名：ningsheng

访问量：4164

签　名：

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

　　自我简介：

TA的其他文章

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

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

你可能喜欢

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

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

　　作者: 凝升　　　　发表时间：2019-08-10 23:56:09 浏览：2124　|　评论：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 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

dotcpp0693251

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

2023-11-19 12:56:00

凝升

TA的其他文章

你可能喜欢

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

1028

C语言考试练习题_保留字母（C语言代码）

破解简单密码（C语言代码）

C语言训练-大、小写问题（C语言代码）

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

评论区

精彩推荐

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

淘淘的名单（C语言代码）答案错误？？？

哥德巴赫曾猜测（C语言代码）

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

The 3n + 1 problem （C语言代码）

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

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

The 3n + 1 problem （C语言代码）

1052题解（链表操作）

数列问题（C语言代码）

凝升

TA的其他文章

你可能喜欢

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

1028

C语言考试练习题_保留字母 （C语言代码）

破解简单密码 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

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

评论区

精彩推荐

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

淘淘的名单 （C语言代码）答案错误？？？

哥德巴赫曾猜测 （C语言代码）

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

The 3n + 1 problem （C语言代码）

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

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

The 3n + 1 problem （C语言代码）

1052题解（链表操作）

数列问题 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

破解简单密码（C语言代码）

C语言训练-大、小写问题（C语言代码）

　　评论区

淘淘的名单（C语言代码）答案错误？？？

哥德巴赫曾猜测（C语言代码）

数列问题（C语言代码）