题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4952
题目的意思很简单:k次operation,第i次x变为最小的k(k>=x && k%i == 0)问最后x为多少。
再一次验证了数学的伟大。表示膜拜,仰慕,ORZ.
对于第i+1次操作,(i +1) * x' >= i *x
x' = x - x / (i +1);
可以看到,当 x < i + 1 的时候,x' = x;也就是说,当i + 1 > x时,以后的操作都是x‘的倍数。那么,我们只需要找到 x’就ok了,ans = k * x'。对于x‘,直接暴力求解就好了。
nx。
Code:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define LL long long int main(){// again , math is amazing LL x, k, i; int cas = 0; while(scanf("%I64d %I64d", &x, &k) && (x + k)){ for(i = 2; i <= k; i ++){ x = x - x / i; if(x < i) break; } printf("Case #%d: %I64d\n", ++ cas, x * k); } return 0; }