(2022牛客多校四)K-NIO‘s Sword(思维)

题目：

样例输入：

4

样例输出：

4

题意：玩家初始有一把攻击力为0的剑，需要依次击杀n个敌人，仅当攻击力模n与i同余才能击杀第i个敌人。而且只能从前往后击杀敌人，也就是说，击杀编号为i的敌人前一定要先击杀编号为i-1的敌人。玩家可以升级剑，每次升级就是将剑的当前攻击力乘以10再加上0~9的一个数，问要想击杀所有的敌人至少要几次升级。

分析：假如我们当前已经击杀了第i个敌人，也就是说现在我们的剑的攻击力ai=k*n+i，我们可以直接将其等价为i，因为比如我们对剑升级了x次，那么剑的攻击力就变为(k*n+i)*10^x+y(y为一个x位数)，等价于k*n*10^x+(i*10^x+y)，那么在modn意义下有没有前面的k*n是没有什么区别的，也就是说，我们直接把击杀第i个敌人后的攻击力看成i即可。现在我们击杀了第i个敌人，也就是说我们现在剑的攻击力是i，那么假设我们升级x后可以击杀第i+1个敌人，也就是说存在一个x位数y使得(i*10^x+y)%n=(i+1)%n,那么就等价于(i+1-i*10^x)%n=y%n，由于y是一个任意的x位数，那么我们只要判断一下(i+1-i*10^x)%n是不是一个x位数即可（可以有前导0），判断的复杂度就是O(1)的，由于n的位数最大是6，所以我们最多需要升级的次数也是6，所以直接暴力判断即可：

需要注意的一个点是n=1时需要特判！

下面是代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e6+10;
int p10[15]={1,10,100,1000,10000,100000,1000000,10000000};
int cnt(long long x)
{
	int ans=0;
	while(x)
	{
		ans++;
		x/=10;
	}
	return ans;
} 
int main()
{
	int n;
	cin>>n;
	if(n==1)
	{
		printf("0");
		return 0;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=6;j++)
		{
			long long x=((i+1-1ll*i*p10[j])%n+n)%n;
			if(cnt(x)<=j)
			{
				ans+=j;
				break;
			}
		}
	}
	printf("%d",ans);
	return 0;
}