3858: Number Transformation
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 82 Solved: 41
[Submit][Status]
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.
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
2520 20
0 0
Sample Output
Case #1: 2520
Case #2: 2600
Case #2: 2600
HINT
Source
其实我也不知道怎么证明，反正通过实验发现n/i每次严格减小到一个极限值，就再也不会变了，而这个极限值在sqrt(n)范围，迭代次数也是sqrt(n)的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long qword;
int main()
{
freopen("input.txt","r",stdin);
qword n,m;
int i;
qword t;
int cnt=;
while (scanf("%lld%lld",&n,&m),cnt++,n+m)
{
t=;
for (i=;i<=m;i++)
{
n=(n/i+(n%i!=))*i;
if (n/i==t)break;
t=n/i;
}
printf("Case #%d: %lld\n",cnt,m*t);
}
}