[题解]最小的01数字串
我不是柳橙汁
2019-11-04 00:49:41
### 题目描述 ###
给定一个正整数$n(1\leq n \leq 10^5)$，求最小的正整数$m$，使得$n\times m$各位数字均为$0$或$1$。
### 题解 ###
首先我们设$f[i]$表示除以$n$余数为$i$的数的位数
然后如果我们用这个数加上一个比他高的$10^k$
就可以这么递推
$$f[(i+10^k)mod \space n]=k$$
我们再建一个pre数组存储反向指针就可以用作输出的处理了
```cpp
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define fd(i,a,b) for(register long long i=a;i>=b;i--)
long long f[100010],pre[100010],num[100010];
long long n;
inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}
int main(){
freopen("1.out","w",stdout);
n=v_in();
if(n==1){//特判1
printf("1 1 1\n");
return 0;
}
f[1]=1,pre[1]=-1;
for(register long long i=2,k=10%n;f[0]==0;i++,k=k*10%n){
fr(j,0,n-1) if(f[j]!=0&&f[j]!=i){//当f[j]到达不了第i位那说明没有必要进行判断
long long t=(j+k)%n;
if(f[t]!=0) continue;//如果已经求出就没有必要再次进行判断
f[t]=i,pre[t]=j;
}
if(f[k]==0) f[k]=i,pre[k]=-1;
}
fr(i,0,100000) printf("%lld %lld\n",f[i],pre[i]);
printf("%lld ",n);
for(register long long i=0;i!=-1;i=pre[i]) num[f[i]]=1;//既然是由某一位推过来的，那当时的最高位也一定是1
long long now=0,flag=0;
fd(i,f[0],1){//按位处理高精
now=now*10+num[i];
if(flag||now>=n){
printf("%lld",now/n);
now%=n;
flag=1;
}
}
printf(" ");
fd(i,f[0],1) printf("%lld",num[i]);//输出
printf("\n");
return 0;
}
```