【LOJ2523】【BZOJ5302】【HAOI2018】奇怪的背包

Author Avatar
q234rty 6月 11, 2018

裴蜀定理+容斥即可。

首先考虑经典的裴蜀定理： \sum_{i=1}^nx_ia_i=d 有整数解当且仅当 \gcd(a_1,a_2,\cdots,a_n) \mid d 。

注意本题并不需要非负的条件，因为可以用 P 来调整。

于是问题就变成了求

\sum_{S\in V_i}[\gcd(S,P)\mid w_i]

首先 V_i 和 w_i 显然都可以先和 P 取 \gcd 。

然后设 k 为 P 的约数个数，根据vfk的blog，当 P\le 10^9 时有 k \le 1344 。

那么我们考虑先对于每个 x\mid P 求出

\sum_{S\in V_i}[x \mid\gcd(S,P)]

显然这就是 2^m-1 ，其中

m=\sum_{i=1}^n[x \mid a_i]

O(k^2) 暴力即可。

之后我们 O(k^2) 暴力容斥求得

\sum_{S\in V_i}[x =\gcd(S,P)]

然后再 O(k^2) 统计答案即可。

时间复杂度 O(k^2+(n+q) \log k) 。

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=20000020;
  5. const int mod=1000000007;
  6. int bufpos;
  7. char buf[MAXSIZE];
  8. #define NEG 0
  9. void init(){
  10. 	#ifdef LOCAL
  11. 		freopen("2532.txt","r",stdin);
  12. 	#endif
  13. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  14. 	bufpos=0;
  15. }
  16. #if NEG
  17. int readint(){
  18. 	bool isneg;
  19. 	int val=0;
  20. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  21. 	bufpos+=(isneg=buf[bufpos]=='-');
  22. 	for(;isdigit(buf[bufpos]);bufpos++)
  23. 		val=val*10+buf[bufpos]-'0';
  24. 	return isneg?-val:val;
  25. }
  26. #else
  27. int readint(){
  28. 	int val=0;
  29. 	for(;!isdigit(buf[bufpos]);bufpos++);
  30. 	for(;isdigit(buf[bufpos]);bufpos++)
  31. 		val=val*10+buf[bufpos]-'0';
  32. 	return val;
  33. }
  34. #endif
  35. char readchar(){
  36. 	for(;isspace(buf[bufpos]);bufpos++);
  37. 	return buf[bufpos++];
  38. }
  39. int readstr(char* s){
  40. 	int cur=0;
  41. 	for(;isspace(buf[bufpos]);bufpos++);
  42. 	for(;!isspace(buf[bufpos]);bufpos++)
  43. 		s[cur++]=buf[bufpos];
  44. 	s[cur]='\0';
  45. 	return cur;
  46. }
  47. int d[2002];
  48. ll cnt[2002];
  49. int pw[1000002];
  50. int main(){
  51. 	init();
  52. 	int n=readint(),q=readint(),p=readint(),cur=0;
  53. 	for(int i=1;i*i<=p;i++)
  54. 		if (p%i==0){
  55. 			d[++cur]=i;
  56. 			if (i*i!=p)
  57. 				d[++cur]=p/i;
  58. 		}
  59. 	sort(d+1,d+cur+1);
  60. 	pw[0]=1;
  61. 	for(int i=1;i<=n;i++){
  62. 		pw[i]=pw[i-1]*2;
  63. 		if (pw[i]>=mod)
  64. 			pw[i]-=mod;
  65. 	}
  66. 	while(n--)
  67. 		cnt[lower_bound(d+1,d+cur+1,__gcd(readint(),p))-d]++;
  68. 	for(int i=1;i<=cur;i++)
  69. 		for(int j=i+1;j<=cur;j++)
  70. 			if (d[j]%d[i]==0)
  71. 				cnt[i]+=cnt[j];
  72. 	for(int i=1;i<=cur;i++)
  73. 		cnt[i]=pw[cnt[i]]-1;
  74. 	for(int i=cur;i;i--){
  75. 		for(int j=i+1;j<=cur;j++)
  76. 			if (d[j]%d[i]==0)
  77. 				cnt[i]-=cnt[j];
  78. 		cnt[i]%=mod;
  79. 	}
  80. 	for(int i=cur;i;i--){
  81. 		for(int j=1;j<i;j++)
  82. 			if (d[i]%d[j]==0)
  83. 				cnt[i]+=cnt[j];
  84. 		cnt[i]=(cnt[i]%mod+mod)%mod;
  85. 	}
  86. 	while(q--)
  87. 		printf("%lld\n",cnt[lower_bound(d+1,d+cur+1,__gcd(readint(),p))-d]);
  88. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/06/11/loj2523/

隐藏