锐客网

  1. 首页 > it技术 > >

搜索|[CF235E]Number Challenge

暴力搜索

题目大意
给定a,b,c<=2000，求 ∑ai=1∑bj=1∑ck=1d(ijk) ，其中 d(n)表示n的因子数量
分析
【搜索|[CF235E]Number Challenge】嗯…题解给出一种鬼畜的解法，它事实上是能过的，我还不知道怎么分析复杂度。
我们知道d()是积性函数嘛，那么我们从大到小考虑质数，记忆化搜索。设f(a,b,c,pt)表示考虑到第pt个质数，三个循环的上界为a,b,c的式子的值。那么很显然 f(a,b,c,pt)=∑f(apri[pt]x,bpri[pt]y,cpri[pt]z,pt?1)?(x+y+z+1) 。然后用哈希存一下就过了…
注意边界条件，当pt到达0，说明所有的质数都考虑过了，那么我们返回1即可，因为即使上界不为1，那些数我们也取不了，因为所有质数都考虑过了。
用map超时，考试千万不要乱用…
另外有两种做法，一种是反演，一种是定理。
代码

#include #include #include #include #include #include #include using namespace std; #define fo(i,j,k) for(i=j; i<=k; i++) #define fd(i,j,k) for(i=j; i>=k; i--) #define cmax(a,b) (a=(a>b)?a:b) typedef long long ll; typedef double db; const int N=2e3+5,mo=1<<30,lim=10000000+5; int pd[N],phi[N],pri[N],a,b,c,i,j,kan,tr[lim+5]; ll feat[lim+5]; void predo() { int n=max(a,max(b,c)),t; fo(i,2,n) { if (!pd[i]) { pri[++pri[0]]=i; phi[i]=i-1; } fo(j,1,pri[0]) { if (1ll*pri[j]*i>n) break; t=pri[j]*i; pd[t]=1; phi[t]=phi[i]*phi[pri[j]]; if (i%pri[j]==0) phi[t]=phi[i]*pri[j]; } } } ll hash(int a,int b,int c,int pt) { ll tp=1ll*a*2001*2001*2001+1ll*b*2001*2001+c*2001+pt; int k=tp%lim; while (tr[k]&&feat[k]!=tp) k=(k+1)%lim; if (!tr[k]) feat[k]=tp; return k; } int dfs(int a,int b,int c,int pt) { //edge if (bif (cif (c

    推荐阅读


    上一篇：android|android 数字进度条--NumberProgressBar

    下一篇：算法|[2016/12/1]判断是否存在重复元素 -- c++ set的巧妙用法