fork(3) download
copy 
  1. /**
  2.     Problem: ACM-ICPC Live Archive 7563 - Coprimes
  3.     Category: Number Theory, Inclusion-Exclusion
  4. **/
  5.  
  6. #include <cstdio>
  7. #include <iostream>
  8. #include <cstring>
  9. using namespace std;
  10.  
  11. #define LL long long
  12. #define NL '\n'
  13. #define xx first
  14. #define yy second
  15. #define pb push_back
  16. #define mp make_pair
  17. #define pii pair<int,int>
  18. #define mem(a,b) memset(a,b,sizeof(a))
  19. #define FOR(i,j,k) for(i=j;i<=k;i++)
  20. #define REV(i,j,k) for(i=j;i>=k;i--)
  21. #define READ(f) freopen(f,"r",stdin)
  22. #define WRITE(f) freopen(f,"w",stdout)
  23. #define pi 2.0*acos(0.0)
  24. #define MOD 1000000007
  25. #define MAX 10005
  26.  
  27. int v[6100][5*MAX];
  28. int sz, bz, a[5*MAX], b[MAX], p[MAX];
  29. LL mob[MAX]={0}, fact[5*MAX], inv[5*MAX];
  30.  
  31. void mobius_sieve(int n)
  32. {
  33.     int status[MAX]={0};
  34.     mem(mob,0);
  35.     sz = 0;
  36.  
  37.     for(LL i = 2; i <= n; i++)
  38.     {
  39.         if(status[i] == 0)
  40.         {
  41.             LL k = i*i;
  42.  
  43.             for(LL j = i; j <= n; j+=i)
  44.             {
  45.                 if((status[j] == 1 && mob[j]==0) || j%k == 0) mob[j] = 0;
  46.                 else mob[j]++;
  47.                 status[j] = 1;
  48.             }
  49.         }
  50.  
  51.         if(mob[i] > 0 && mob[i]%2 == 1)
  52.         {
  53.             mob[i] = -1;
  54.             p[sz++] = i; // save only necessary elements
  55.         }
  56.         else if(mob[i] > 0 && mob[i]%2 == 0)
  57.         {
  58.             mob[i] = 1;
  59.             p[sz++] = i;
  60.         }
  61.     }
  62. }
  63.  
  64. // For fermat's theorem below
  65. LL bigmod(LL n, LL p, LL m)
  66. {
  67.     if(p == 0) return 1;
  68.     if(p == 1 || n == 1) return n % m;
  69.  
  70.     LL ret = bigmod(n, p/2, m);
  71.     ret = (ret * ret) % m;
  72.     if(p % 2) ret = (ret * n) % m;
  73.     return ret%m;
  74. }
  75. // Farmat's rule requires b to be prime
  76. LL mod_inverse(LL a, LL b)
  77. {
  78.     return bigmod(a, b-2, b);
  79. }
  80.  
  81. void init()
  82. {
  83.     // mobius function
  84.     // generate factorials
  85.     // generate modular inverse of factorials
  86.     mobius_sieve(10000);
  87.  
  88.     fact[0] = 1;
  89.     inv[0] = mod_inverse(fact[0], MOD);
  90.  
  91.     for(LL i = 1; i < 50002; i++)
  92.     {
  93.         // factorials
  94.         fact[i] = (fact[i-1] * i) % MOD;
  95.         // modular inverse of factorials
  96.         inv[i] = mod_inverse(fact[i], MOD);
  97.     }
  98. }
  99.  
  100. int main()
  101. {
  102.     //READ("in.txt");
  103.     //WRITE("out.txt");
  104.     int cases, caseno=0, n, i, j, k, q, l, r, cnt;
  105.     LL x, ans;
  106.  
  107.     init();
  108.  
  109.     while(scanf("%d", &n)==1)
  110.     {
  111.         FOR(i,0,n-1)
  112.             scanf("%d", &a[i]);
  113.  
  114.         bz = 0;
  115.         // pre-process the array, O(sz * n) where sz = 6082
  116.         FOR(i,0,sz-1)
  117.         {
  118.             v[i][0] = 0;
  119.             if(a[0] % p[i] == 0) v[i][0]++;
  120.  
  121.             FOR(j,1,n-1)
  122.             {
  123.                 v[i][j] = v[i][j-1];
  124.                 if(a[j] % p[i] == 0) v[i][j]++;
  125.             }
  126.  
  127.             if(v[i][n-1] > 0) b[bz++] = i;
  128.         }
  129.  
  130.         scanf("%d", &q);
  131.  
  132.         while(q--)
  133.         {
  134.             scanf("%d %d %d", &l, &r, &k);
  135.  
  136.             ans = (fact[r-l+1] * inv[k]) % MOD;
  137.             ans = (ans * inv[r-l+1-k]) % MOD;
  138.  
  139.             FOR(i,0,bz-1)
  140.             {
  141.                 cnt = v[ b[i] ][r-1];
  142.                 if(l > 1) cnt -= v[ b[i] ][l-1];
  143.  
  144.                 if(cnt >= k)
  145.                 {
  146.                     // using nck = n! / (k! * (n-k)!)
  147.                     x = (fact[cnt] * inv[k]) % MOD;
  148.                     x = (x * inv[cnt-k]) % MOD;
  149.                     x = mob[p[ b[i] ]] * x;
  150.                     x = (x + MOD) % MOD;
  151.                     ans = (ans + x) % MOD;
  152.                 }
  153.             }
  154.  
  155.             printf("%lld\n", ans);
  156.         }
  157.     }
  158.  
  159.     return 0;
  160. }
  161.  
Runtime error #stdin #stdout 0s 144KB
comments (?)
stdin
copy 
10
1 2 3 4 5 6 7 8 9 10
3
1 5 2
1 10 3
1 10 4
stdout
copy 
Standard output is empty
https://ideone.com/5yszjX
LiveArchive - Coprimes
language:
C++ (gcc 8.3)
created:
8 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!