2014多校 第八题 1008

2014 Multi-University Training Contest 8

大意：输入x和k，进行k次操作，每次把x变成大于等于x的最小的k的倍数，求最后的x。(1<=x k <=10^10)

题解：怒找规律。

这个的暴力做法很好写，几行就写出来了：

         now=x;
         for(i=;i<=k;i++){
             mo=now%i;
             if(mo!=){
                 now+=i-mo;
             }
         }

↑这个是比纯暴力优化了一点的，因为已知余数就可以直接算得下一个x，不用一个个加一个个试。

但是这样还是会超时得飞起来，10^10的数据必须找比O(n)小的方法。

于是我们可以在循环里面输出各种mo、i-mo、now之类的数，输入一点大数据观察一下有没有规律。

然后可以发现每次到后期，i-mo都会变成一个固定值！虽然我也不懂为什么，不过知道这个就可以了。当我们发现进入了这个状态时，直接now+=(不变的i-mo)*(k-i)，得到最后结果。

于是我们统计i-mo连续多少次不变的次数，达到一定值就认为永远不变了，直接算。这个有时候也会出现连续5个不变之后又变了的，所以我设的是100次，多个100而已，对整体影响很小。

 ll farm(ll x,ll k) {
     ll i,now,mo;
     ll pre,cnt,maxc=;
     pre=-;
     cnt=;
     now=x;
     for(i=; i<=k; i++) {
         mo=now%i;
         if(mo!=) {
             now+=i-mo;
         }
         if(cnt>=maxc) {
             now+=pre*(k-i);
             break;
         }
         if(i-mo==pre)cnt++;
         else cnt=;
         pre=i-mo;
     }
     return now;
 }

全代码：

 //#pragma comment(linker, "/STACK:102400000,102400000")
 #include<cstdio>
 #include<cmath>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 #include<cmath>
 #include<map>
 #include<set>
 #include<stack>
 #include<queue>
 using namespace std;
 #define ll long long
 #define usint unsigned int
 #define mz(array) memset(array, 0, sizeof(array))
 #define minf(array) memset(array, 0x3f, sizeof(array))
 #define REP(i,n) for(i=0;i<(n);i++)
 #define FOR(i,x,n) for(i=(x);i<=(n);i++)
 #define RD(x) scanf("%d",&x)
 #define RD2(x,y) scanf("%d%d",&x,&y)
 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
 #define WN(x) printf("%d\n",x);
 #define RE  freopen("D.in","r",stdin)
 #define WE  freopen("1biao.out","w",stdout) ll farm(ll x,ll k) {
     ll i,now,mo;
     ll pre,cnt,maxc=;
     pre=-;
     cnt=;
     now=x;
     for(i=; i<=k; i++) {
         mo=now%i;
         if(mo!=) {
             now+=i-mo;
         }
         if(cnt>=maxc) {
             now+=pre*(k-i);
             break;
         }
         if(i-mo==pre)cnt++;
         else cnt=;
         pre=i-mo;
     }
     return now;
 } int main() {
     int cas=, ans;
     ll x,k,now,i,mo,pre,ppre,flag;
     while(scanf("%I64d%I64d",&x,&k)!=EOF) {
         if(x== && k==)break;
         printf("Case #%d: %I64d\n",cas++,farm(x,k));
     }
     return ;
 }