hdu4952 Number Transformation （找规律）

时间：2022-05-30 20:05:38

2014多校 第八题 1008

2014 Multi-University Training Contest 8

4952 Number Transformation

Number Transformation

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 85 Accepted Submission(s):
31

Problem Description
Teacher Mai has an integer x.

He does the
following operations k times. In the i-th operation, x becomes the least integer
no less than x, which is the multiple of i.

He wants to know what is the
number x now.

 
Input
There are multiple test cases, terminated by a line "0
0".

For each test case, the only one line contains two integers
x,k(1<=x<=10^10, 1<=k<=10^10).

 
Output
For each test case, output one line "Case #k: x", where
k is the case number counting from 1.
 
Sample Input
2520 10
2520 20
0 0
 
Sample Output
Case #1: 2520
Case #2: 2600
 
Source
 
Recommend
hujie

大意：输入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 ;

 }

相关文章