锐客网

  1. 首页 > it技术 > >

[bzoj3462]dzy loves math II 解题报告

数论

这道题的题意是设 S=∏ki=1pi ,且 n=∑ki=1xipi,xi≥1 ,求 (x1,x2,...,xk) 的个数。
对于任一 (x1,x2,...,xk) ，显然其可射于 (x1 modSp1,x2 modSp2,...,xk modSp3) ，而且有 ∑ki=1xipi≡n(mod S) 。对于后者，其实就是一个多重背包；然后从它到n就是将若干个S分成k份，这便是一个经典问题了。
那么主要的时间就都花在多重背包上了， 2?106 以内的数质因子个数最多有7个，所以时间复杂度就是 O(72?S+7?q)≈108

#include int f[15000000],fp[15000000]; int prime[1505]; bool p[1505]; #include using namespace std; #include int a[10]; #define Mod 1000000007 typedef long long LL; void in(LL &x){ char c=getchar(); while(c<'0'||c>'9')c=getchar(); for(x=0; c>='0'&&c<='9'; c=getchar())x=x*10+(c^'0'); } int inver(int x){ LL ans=1,pro=x; for(int pow=Mod-2; pow; pow>>=1,pro=pro*pro%Mod) if(pow&1) ans=ans*pro%Mod; return ans; } #include int main(){ freopen("bzoj_3462.in","r",stdin); freopen("bzoj_3462.out","w",stdout); int S,q,i,root,j; scanf("%d%d",&S,&q); //线筛 for(i=2,root=sqrt(S); i<=root; ++i){ if(!p[i]){ prime[++prime[0]]=i; if(S%i==0){ //cout<<"Get:"<=0&&i<=sum; i+=S,--N,--n){ pro=pro*inver(n+a[0])%Mod*(n+1)%Mod; ans=(ans+f[i]*pro)%Mod; /*printf("%d(%d)*%I64d(%I64d,%d)=%I64d\n",f[i],i,pro,n+a[0]-1,a[0]-1,f[i]*pro%Mod); cout<

【[bzoj3462]dzy loves math II 解题报告】我犯的错误：
①分解质因数时忘了考虑大于 S??√ 的质因子。
②没注意到需要保证 x≥1 .

    推荐阅读


    上一篇：阿博随笔2019-10-16

    下一篇：（Div.2）D.|（Div.2）D. Edge Deletion