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 ;
}