fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Numeric Constants
  5. #define N 1000000007
  6. #define maxs 1000005
  7. #define mins 1005
  8. #define eps 1e-14
  9. #define imax 2000000200
  10. #define llmax 1000000002000000000ll
  11. #define pi 3.141592653589793
  12.  
  13. // Others
  14. #define ll long long
  15. #define pb push_back
  16. #define gc getchar_unlocked
  17. #define iosbase ios_base::sync_with_stdio(false)
  18. #define pii pair<int,int>
  19. #define pll pair<ll,ll>
  20. #define ppi pair<pair<int,int>,int>
  21. #define ppl pair<pll,ll>
  22. #define vi vector<int>
  23. #define sc scanf
  24. #define pr printf
  25. #define lld I64d
  26. #define F first
  27. #define S second
  28. #define siter set<int>::iterator
  29. #define p_pq priority_queue
  30. #define ub upper_bound
  31. #define lb lower_bound
  32.  
  33. ll ans[maxs],a[maxs],mark[maxs],cnts[maxs];
  34. ll tot[maxs];
  35.  
  36. ll power(ll a,ll b,ll c){
  37. 	ll t=1;
  38. 	while(b){
  39. 		if(b&1){
  40. 			t=(t*a)%N;
  41. 		}
  42. 		a=(a*a)%N;
  43. 		b>>=1;
  44. 	}
  45. 	return t;
  46. }
  47.  
  48. int main()
  49. {
  50. 	int n,q,i,j,t,k;
  51. 	sc("%d",&n);
  52. 	for(i=0;i<n;i++){
  53. 		sc("%lld",&a[i]);
  54. 		cnts[a[i]]++;
  55. 	}
  56. 	for(i=1;i<=1000000;i++){
  57. 		for(j=i,t=1;j<=1000000;j+=i,t++){
  58. 			if(i!=t){
  59. 				tot[j]+=cnts[i]*cnts[t];
  60. 			}
  61. 			else{
  62. 				tot[j]+=cnts[i]*(cnts[i]-1);
  63. 			}
  64. 			tot[j]%=N;
  65. 		}
  66. 	}
  67. 	for(i=1;i<=1000000;i++){
  68. 		for(j=i;j<=1000000;j+=i){
  69. 			ans[j]+=tot[i];
  70. 			ans[j]%=N;
  71. 		}
  72. 	}
  73. 	for(i=1;i<=1000000;i++){
  74. 		ans[i]=(ans[i]*power(2,N-2,N));
  75. 		ans[i]%=N;
  76. 	}
  77. 	sc("%d",&q);
  78. 	for(i=0;i<q;i++){
  79. 		sc("%d",&k);
  80. 		pr("%lld\n",ans[k]);
  81. 	}
  82. 	return 0;
  83. }
Runtime error #stdin #stdout 0.68s 42528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gPM7Hh
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!