lalalala


私信TA

用户名:zhangshuo

访问量:151549

签 名:

像狗一样的学习,像绅士一样地玩耍。

等  级
排  名 5
经  验 30084
参赛次数 10
文章发表 201
年  龄 12
在职情况 学生
学  校 芜湖市第十一中学
专  业

  自我简介:

今日懒惰流下的口水,将会成为明日里伤心的泪水。

解题思路:

考察高精,累乘。

循环条件:原数*累乘器=原数。

此时:原数*累乘器=原数。

即乘n个累乘器,已匹配的位数不改变。

1位位地匹配,如果某一位出现11个数字,则必定没有循环。

注意每一位匹配后,累乘器要更新。






注意事项:





参考代码:

#include<cstdio>
#include<cstring>
int ans[101];
int a[101],n=0,k;
int i,j,rec[101],newn[101];
char ch[101];
bool judge(int k) //计算是否循环 
{    
int s[102];    
memset(s,0,sizeof(s));    
for (int i=1; i<=n; i++)      
for (int j=1; j<=newn[0]; j++)        
if (i+j-1 > k) break;       
else
        {
           s[i+j-1]+=a[i]*newn[j];
           s[i+j]+=s[i+j-1]/10;
           s[i+j-1]%=10;
        }    
if (s[k] == a[k]) 
return 1;    
return 0;
}
void mul() //累乘 
{    
int s[102];    
memset(s,0,sizeof(s));    
for (int i=1; i<=rec[0]; i++)      
for (int j=1; j<=newn[0]; j++)        
if (i+j-1 <= n)
        {
           s[i+j-1]+=rec[i]*newn[j];
           s[i+j]+=s[i+j-1]/10;
           s[i+j-1]%=10;
        }   
 if (rec[0]+newn[0]-1 >= n) s[0]=n;    
 else if (s[rec[0]+newn[0]] > 0) s[0]=rec[0]+newn[0];    
 else s[0]=rec[0]+newn[0]-1;    
 for (int i=0; i<=s[0]; i++)
      newn[i] = s[i];
}
 void calc(int x) //单精*高精 
 {    
    for (int i=1; i<=ans[0]; i++)
      ans[i]*=x;    
    for (int i=1; i<=ans[0]; i++)
    {
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
    }    
    while (ans[ans[0]+1] > 10)
    {
        ans[0]++;
        ans[ans[0]+1]+=ans[ans[0]]/10;
        ans[ans[0]]%=10;
    }    
    if (ans[ans[0]+1] > 0) ans[0]++;
}
    int main()
    {    
    scanf("%c",&ch[++n]);    
    while (ch[n] != ' ')      
    scanf("%c",&ch[++n]);    
    scanf("%d",&k);
    n--;    
    for (i=1; i<=n; i++)
      a[i]=ch[n+1-i]-'0';    
    if (n > k) n=k;    
    if (n < k) 
    {      
    for (i=n+1; i<=k; i++)
        a[i] = 0;
        n = k;
    } //init
    for (i=1; i<=n; i++)
      rec[i]=a[i]; //last one 加数 
    rec[0]=n; 
    for (i=1; i<=n; i++)
    newn[i]=a[i]; 
    newn[0]=n; //rec^x (累乘器)
    ans[0]=1; 
    ans[1]=1;    
    for (i=1; i<=k; i++)
    {        
    if (judge(i)) continue; //第i位相等 
        else 
    for (j=2; j<=11; j++)
        {
            mul(); //累乘器 
            if (judge(i)) break;
        }        
    if (j > 11) //无解 
        {            
           printf("-1");            
           return 0;
        }        
        calc(j); //ans=ans*j;
        for (j=newn[0]; j>=0; j--)
          rec[j]=newn[j];
    }    
        for (i=ans[0]; i>=1; i--)      
        printf("%d",ans[i]);    
        return 0;
}


 

0.0分

5 人评分

  评论区

感谢大佬。j>11无解是不是因为由鸽巢原理第i位一定有数出现两回,构成了没有a[i]的循环(比i低的位已经可以循环了)。这个把k位存在循环转化成从低到高检查每位是否可以循环的方法太巧妙了!
2019-12-03 21:35:00
  • «
  • 1
  • »