Prime Cryptarithm

2019-11-06 06:33:49

字体：大中小

来源：转载

供稿：网友

这题本来是道水到不行的暴力题，然而这样做复杂度大。可以用哈希搞一个 O(1) $O(1)$ 的算法，可以达到全部测试点 0ms 的效果。

思路：开一个bool型的hash数组，先用进制枚举法（N进制）位所有的可用数字标为true，再枚举所有情况。

代码：

/*ID:zhangch33LANG:C++TASK:crypt1*/#include<iostream>#include<cstdio>using namespace std;bool hash[10000];int num[10];int N;int mypow(int x,int y){ int res=1; while(y--) res*=x; return res;}inline void initHash(){ int i,j,k; for(k=2;k<=4;k++) for(i=0;i<=10000;i++) { int res=0,x=i; for(j=1;j<=mypow(10,k-1);j*=10) res+=num[x%N]*j,x/=N; hash[res]=true; }}int main(){ freopen("crypt1.in","r",stdin); freopen("crypt1.out","w",stdout); int i,j; scanf("%d",&N); for(i=0;i<N;i++) scanf("%d",&num[i]); /// initHash(); /// int a,b; int ans=0; for(a=100;a<=999;a++) { if(!hash[a]) continue; for(b=10;b<=99;b++) { if(!hash[b]) continue; int c=a*(b%10),d=a*(b/10),e=a*b; if(c>999||c<99) continue; if(!hash[c]) continue; if(d>999||d<99) continue; if(!hash[d]) continue; if(e>9999||e<999) continue; if(!hash[e]) continue; ans++; } } PRintf("%d/n",ans); return 0;}

上一篇：使用ServletContextListener监听器

下一篇：【算法】程序猿不写代码是不对的25