fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int mod = 1009;
  5. #define pb push_back
  6. #define F first
  7. #define S second
  8. #define fills(x,y) memset(x,y,sizeof x)
  9. #define rep(i,n) for(i=0;i<n;++i)
  10. #define REP(i,k,n) for(i=k;i<=n;++i)
  11. #define tr(i,c) for(auto &i:c)
  12. #define fastio          ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  13. #define inchar          getchar
  14. #define outchar(x)      putchar(x)
  15. #define bitcounts(n) __builtin_popcountll(n)
  16. #define sz(a) int((a).size())
  17. #define endl "\n"
  18. template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
  19. template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
  20. template<typename T> void scan(T &x){x=0;bool neg=0;register T c=inchar();if(c=='-')
  21. neg=1,c=inchar();while((c<48)||(c>57))c=inchar();for(;c<48||c>57;c=inchar());
  22. for(;c>47&&c<58;c=inchar())x=(x<<3)+(x<<1)+(c&15);if(neg)x*=-1;}
  23. template<typename T> void output(T n){bool neg=0;if(n<0)n*=-1,neg=1;char snum[65];int i=0;do {snum[i++]=n%10+'0';n/=10;}\
  24. while(n);i=i-1; if(neg)putchar('-'); while(i>=0)outchar(snum[i--]);outchar('\n');}
  25. inline void instr(char *str){register char c=0;register int i=0;while(c<33)c=inchar();while (c!='\n'&&c!=' '&&c!=EOF){\
  26. str[i]=c;c=inchar();++i;}str[i]='\0';}
  27. template<typename T> T lcm(T a, T b){return (a*(b/__gcd(a,b)));}
  28. template<typename T> inline T MOD(T a, T b) {return (a<b ? a : a%b);}
  29. template<typename T> T add(T a, T b, T c){T x=a+b;return (x>=c ? x-c : x);}
  30. template<typename T> T mod_neg(T a, T b) {a=MOD(a, b);if(a<0){a+=b;}return a;}
  31. template<typename T> T expo(T e, T n){T x=1,p=e;while(n){if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
  32. template<typename T> T power(T e, T n, T m){T x=1,p=e;while(n){if(n&1)x=MOD(x*p,m);p=MOD(p*p,m);n>>=1;}return x;}
  33. template<typename T> T exted_euclid(T a, T b, T &x, T &y){T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;t=xx;\
  34. xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
  35. template<typename T> T mod_inverse(T a, T n){T x,y;T d = exted_euclid(a, n, x, y);return (d>1?-1:mod_neg(x,n));}
  36. #define tcsolve() int tcs; cin>>tcs;while(tcs--) solve();
  37.  
  38. const int MAX=500;
  39. int arr[MAX];
  40.  
  41. void solve()
  42. {
  43. int m,n,i,j,a,p,q,x=0,y=0,both=0, rem = 0;
  44. scanf("%d,%d,%d",&n,&p,&q);
  45.  
  46. for(int i=0; i<n; ++i){
  47.     scanf("%d,", &a);
  48.     if(a % (p*q) == 0)
  49.         ++both;
  50.     else if(a%p==0 && a%q!=0)
  51.         ++x;
  52.     else if(a % q == 0)
  53.         ++y;
  54.     else
  55.         ++rem;
  56. }
  57.  
  58. long long  ans = ((power(2,x,mod) -1 )* (power(2,y,mod) - 1)) % mod  * (power(2,rem, mod));
  59. ans = (ans%mod +  (power(2,both, mod) - 1) * power(2,rem+y+x, mod)) % mod;
  60.  
  61. cout << ans;
  62. }
  63.  
  64. int  main()
  65. {
  66. #ifdef LOCAL
  67. freopen("in.c","r",stdin);
  68. //freopen("out.c","w",stdout);
  69. #endif
  70. solve();
  71. return 0;
  72. }
  73.  
Success #stdin #stdout 0s 4276KB
comments (?)
stdin
copy 
4,5,7
5,49,10,27
stdout
copy 
6
https://ideone.com/XyblHd
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!