这是在dp的专题里写了,想了半天的dp,其实就是暴力。。。
题目大意:给你一个n,问你在30位以内有没有一个只由1或2 构成的数被 n 整除,如果
有则输出最小的那个,否则输出Impossible。
思路:因为位数是30,所以我们不能直接暴力,这样的复杂度是2^30次。那么其实我们
可以分段暴力,我们只要求出15位的所有余数的最小值,我们再处理处由15数字组成的余数,
如果答案超过十五位,我们枚举超过15位部分的余数,找对应需要的余数。
#include<bits/stdc++.h> #define ll long long using namespace std; ll dp[1000005],f[1000005],n; void dfs(ll pos,ll now) { ll mod=now%n; if(now && (dp[mod]>now || !dp[mod])) dp[mod]=now; if(pos==15) { if(!f[mod] || f[mod]>now) f[mod]=now; return; } dfs(pos+1,now*10+1); dfs(pos+1,now*10+2); } int main() { cin>>n; if(n==1) { puts("1"); return 0; } if(n==2) { puts("2"); return 0; } dfs(0,0); if(dp[0]) { cout<<dp[0]<<endl; return 0; } ll ans1=-1,ans2=-1; for(ll i=1;i<n;i++) { if(!dp[i]) continue; ll now=i; for(int j=1;j<=15;j++) { now=now*10%n; } ll p=n-now; if(!f[p]) continue; if(ans1==-1 || ans1>dp[i]) { ans1=dp[i]; ans2=f[p]; } } if(ans1==-1) puts("Impossible"); else printf("%I64d%I64d ",ans1,ans2); return 0; }