题解 CF1350A 【Orac and Factors】

CF 1350A 一道数学题（雾）

暴力

首先我们不难想到一种暴力写法。每次寻找下一个数，然后操作k次。最后输出。那么代码如下

#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代码：

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