NIO‘s Sword(牛客多校赛)

题目链接
题意：
1：给一个数n
2：要求按顺序消灭1~n的敌人
3：给一个数据A，初始值为0
4：每次可以对A进行一个操作，使得A=10*A+x，(0<=x<=9)
5：当A%n==i%n的时候，才可以消灭第i个敌人
求消灭所有的敌人需要的最小操作数：
题解：当我们正在消灭第i个敌人时，我们是已知A(i-1)%n == i-1的，所以所以上一个数保持原数是肯定不能的，即A(i-1)%n!=i，所以我们必须对其进行一次操作。我们现在可能考虑到前面取不同的值可能对当前%n的余数造成影响，但是其实是不会影响的，我们假设A(i-1)%n=i-1，那么不论A(i-1)是多少，(10 * A(i-1) + x ) % n = (10 * A(i-1) %n + x%n ) % n=((10 % n * A(i-1) %n ) % n + x %n )%n，因为这里不一定是1所以可能是10^k所以我们进一步化简原式=((10 ^ k % n * A(i-1) %n ) % n + x %n )%n=( (i-1) * (10 ^ k % n) + x ) % n= i ，这样我们会发现，无论A(i-1)取多少，都不会对当前的数造成影响。所以，只要我们找到最小的满足的就可以。

现在我们的问题变成了找到了对i来说最小的满足情况的值，这里因为x是0~9的所以我们会发现，(10*x1+x2) * 10 + x3 ……，这样循环下去，我们可以表示所有 0 ~ (10^k)-1的所有的值，这样因为n是1e6的，所以最多6位就可以将所有的余数表示出来，这样的话，我们直接枚举即可

下面是AC代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int pw[20];
int n;
int A;
int check(int len,int i)
{
    
     int res=A*(pw[len]%n);
     res%=n;
     int need=(i-res+n)%n;//这里我们对应公式就是我们需要的xi
     if(need<pw[len]) return 1;//如果比当前能够形成的数小，就可以ok
     else return 0;
}
signed main()
{
    
    cin>>n;
    pw[0]=1;
    for(int i=1;i<=15;i++) pw[i]=pw[i-1]*10;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
    
        for(int j=0;j<=6;j++)
        {
    
            if(check(j,i))
            {
    
                A=i;
                ans+=j;
                break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}