题解 CF1350A 【Orac and Factors】
smallfang
2020-05-14 22:05:29
CF 1350A 一道数学题（雾）
## 暴力
首先我们不难想到一种暴力写法。每次寻找下一个数，然后操作$k$次。最后输出。那么代码如下
```cpp
#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n, k;
int f(int x)
{
for(int i = 2; i <= x; i ++ )
{
if(x % i == 0)
{
return i;
}
}
return -1;
}
int main()
{
int t;
scanf("%d", &t);
while ( t -- )
{
scanf("%d%d", &n, &k);
int ans = n;
for(int i = 1; i <= k; i ++ )
{
ans += f(ans);
}
printf("%d\n", ans);
}
return 0;
}
```
显然，这样的操作次数高达$10^{11}$。所以我们可以通过~~找规律~~和数学研究得出答案。
## 找规律
我们可以进行一些有规律的测试。发现每个数在操作>1次的时候，每次都会比前面的大2.而且第一次就是$f(number)$所以我们我们就可以得到$ans = res + f(res), ans = (n - 1) * 2$
## 证明
当然我们可以证明。证明如下。
首先我们进行第一步的模拟。
首先有两种可能，这是一个偶数，或者这是一个奇数。
首先看偶数，每次都会找到2，因为要除1之外嘛。
偶数+2=偶数，所以会陷入无限循环。
其次看奇数，奇数没有偶因子。所以一定找到的是一个奇数，奇数+奇数肯定等于偶数。便到了偶数判定，进入循环。
所以我们会发现，除了第一次有区别之外，其他都会+2。由此，此题搞定。
AC代码：
```cpp
#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int ctf[10001];
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int t;
scanf("%d", &t);
int res = 0;
while (t--)
{
int x;
scanf("%d", &x);
int y = x, res = 0, cnt = 0;
while (y >= 10)
{
res += (y % 10) > 0;
y /= 10;
}
res += (y % 10) > 0;
printf("%d\n", res);
y = x;
while (y >= 10)
{
if (y % 10)
{
printf("%d", y % 10);
for (int i = 1; i <= cnt; i++)
{
printf("0");
}
printf(" ");
}
y /= 10;
cnt++;
}
if (y != 0)
{
printf("%d", y);
for (int i = 1; i <= cnt; i++)
printf("0");
}
printf("\n");
}
return 0;
}
```