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的时候,to destroy the firsti个敌人
Find the minimum number of operations required to destroy all enemies：
题解：when we are eradicating thi个敌人时,we are knownA(i-1)%n == i-1的,Therefore, it is absolutely impossible to keep the previous number as the original number,即A(i-1)%n!=i,So we have to operate on it once.We may now take into account that the previous take a different value may be for the current%nimpact on the remainder,But it doesn't actually affect it,我们假设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,Because it doesn't have to be here1所以可能是10^kSo we further simplify the original formula=((10 ^ k % n * A(i-1) %n ) % n + x %n )%n=( (i-1) * (10 ^ k % n) + x ) % n= i ,这样我们会发现,无论A(i-1)取多少,will not affect the current number.所以,As long as we find the smallest satisfaction.

Now our problem becomes finding the rightiThe smallest value that satisfies the situation,这里因为x是0~9so we will find out,(10*x1+x2) * 10 + x3 ……,这样循环下去,We can mean all 0 ~ (10^k)-1的所有的值,这样因为n是1e6的,所以最多6bits can represent all remainders,这样的话,We can just enumerate directly

下面是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;//Here our corresponding formula is what we needxi
     if(need<pw[len]) return 1;//If it is smaller than the number that can currently be formed,就可以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;
}