fork(1) download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <math.h>
  4. #include <map>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <string.h>
  8. #include <stdlib.h>
  9. #include <set>
  10. #define mod 1000000007
  11. #define ll long long
  12. #define pb push_back
  13. #define mp make_pair
  14. #include <queue>
  15.  
  16. using namespace std;
  17.  
  18. long long gcd( long long a , long long b )
  19. {
  20.     return b == 0 ? a : gcd( b , a%b );
  21. }
  22.  
  23. long long power( long long a , long long b )
  24. {
  25.     long long ret = 1 ;
  26.     while( b ) {
  27.       if( b%2 == 1 ) ret = ( ret * a ) % mod ;
  28.       a = ( a * a ) % mod ;
  29.       b /= 2 ;
  30.     }
  31.     return ret ;
  32. }
  33.  
  34. #define N 100010
  35. int primes[ 333 ] , number[ N ];
  36. bool isprime[ N ];
  37. int arr[ N ] ;
  38. char segtree[ 67 ][ 21 ][ N ];
  39.  
  40. #define mid(L,R) ((L+R)/2)
  41. struct Node{ int cnt , L , R;
  42.     Node()
  43.     {
  44.         cnt = 1 ;
  45.         L = R = -1;
  46.     }
  47.     Node( int x,int y,int z)
  48.     {
  49.         L = x;
  50.         R = y;
  51.         cnt = z;
  52.     }
  53. }tree[6000001];
  54.  
  55. int G[N];
  56. int root[N] , RM[N] , B[N] , V[N] ;
  57. int gc = 0 ;
  58.  
  59. int build(int L , int R)
  60. {
  61.     ++gc;
  62.     if( L == R )
  63.         return gc;
  64.     int x = gc;
  65.     tree[x] = Node(build(L,mid(L,R)),build(mid(L,R)+1,R),1);
  66.     return x;
  67. }
  68.  
  69.  
  70.  int update(int L , int R , int root , int idx , int val  )
  71. {
  72.     if( L > idx || R < idx )
  73.         return root;
  74.     ++gc;
  75.  
  76.     if( L == idx && R == idx )
  77.     {
  78.         tree[gc] = Node(-1 ,-1 , (1LL*tree[root].cnt*val)%mod );
  79.         return gc;
  80.     }
  81.     int x = gc;
  82.     tree[x] = Node( update(L,mid(L,R),tree[root].L,idx,val), update(mid(L,R)+1,R,tree[root].R,idx,val),(1LL*tree[root].cnt*val)%mod );
  83.  
  84.     return x;
  85. }
  86.  
  87. long long int query(int L , int R , int root , int qe , int qr )
  88. {
  89.     if(qr<L || qe>R)return 1;
  90.     if(qe <=L && R <= qr) {
  91.         //cout << "Hi " << L << " " << R << " " << tree[ root ].cnt << endl ;
  92.         return tree[root].cnt;
  93.       }
  94.     return ( 1LL*query(L,mid(L,R),tree[root].L,qe,qr) * query(mid(L,R)+1,R,tree[root].R,qe,qr))%mod;
  95. }
  96.  
  97. long long int primepower[ 32 ][333 ];
  98.  
  99. int solve( int x , int y )
  100. {
  101.     int ans =0 ;
  102.     while ( x%y == 0 ) {
  103.       x /= y ;
  104.       ans++ ;
  105.     }
  106.     return ans;
  107. }
  108.  
  109. int twopower[ 25 ] , log_arr[ N ];
  110.  
  111. int main()
  112. {
  113.    twopower[ 0 ] = 1 ;
  114.  
  115.    for( int i = 1 ; i < 25 ; i++ ) twopower[ i ] = 2*twopower[ i - 1 ];
  116.  
  117.    for( int i = 1 ; i < N ; i++ ) {
  118.      log_arr[i] = floor(log2(i));
  119.    }
  120.    int n , q;
  121.  
  122.    for( int i = 2 ; i*i < N ; i++  ) {
  123.      if( isprime[i] == 0 )
  124.       for( int j = 2*i ; j < N ; j+= i )
  125.         isprime[ j ] = 1;
  126.    }
  127.  
  128.    for( int i = 1 ; i < N ; i++ )
  129.     number[ i ] = 1 ;
  130.  
  131.    for( int i = 334 ; i < N ; i++ )
  132.     if( isprime[ i ] == 0 )
  133.       for( int j = i ; j < N ; j += i )
  134.         number[ j ] = i ;
  135.  
  136.    int counter = 0 ;
  137.  
  138.    for( int i = 2 ; i <= 333 ; i++ )
  139.     if( isprime[ i ] == 0 )
  140.       primes[ counter++ ] = i ;
  141.  
  142.  
  143.    scanf("%d%d", &n , &q );
  144.  
  145.    for( int i = 1 ; i <= n ; i++ ) scanf("%d", &arr[i] );
  146.  
  147.    for( int i = 0 ; i < counter ; i++ )
  148.    {
  149.      //cout << i << " "  << endl ;
  150.      for (int j = 1 ; j <= n ; j ++)
  151.          segtree[ i ][ 0 ][ j ] = (char)(solve( arr[ j ] , primes[ i ] ));
  152.  
  153.      for (int j = 1; 1 << j <= n; j++)
  154.          for (int k = 1 ; k + (1 << j) - 1 <= n ; k++ )
  155.             if ( segtree[ i ][j - 1][ k ] >= segtree[ i ][j - 1][k + (1 << (j - 1))] )
  156.               segtree[ i ][ j ][ k ] = segtree[ i ][ j - 1 ][ k ];
  157.             else
  158.               segtree[ i ][ j ][ k ] = segtree[ i ][j - 1][k + (1 << (j - 1))];
  159.    }
  160.  
  161.    for( int i = 1 ; i <= n ; i++ ) {
  162.     arr[ i ] = number[ arr[ i ] ] - 1 ;
  163.  
  164.     if( arr[ i ] == 0 )
  165.       arr[ i ] = 1 ;
  166.   }
  167.  
  168.    memset(G,-1,sizeof(G));
  169.    root[0] = build( 1 , n );
  170.    for( int i = 1 ; i <= n ; ++i )
  171.    {
  172.         int p = root[ i - 1 ];
  173.         if( G[ arr[i] ] != -1 )
  174.             p = update( 1, n, p, G[arr[i]], power( arr[ i ] , mod - 2 ) );
  175.         root[i] = update(1 , n, p, i, arr[ i ] );
  176.         G[arr[i]] = i;
  177.    }
  178.  
  179.    long long a , b , c , d ;
  180.    cin >> a >> b >> c >> d ;
  181.  
  182.    for( int i = 0 ; i < counter ; i++ ) {
  183.      long long phi = primes[ i ] - 1 , mul = phi ;
  184.      primepower[ 0 ][ i ] = 1 ;
  185.      //cout
  186.      for( int j = 1 ; j < 32 && phi < N ; j++ , phi *= mul )
  187.       primepower[ j ][ i ] = phi ;
  188.    }
  189.    //cout <<" COunter is " << counter << endl ;
  190.  
  191.    long long ans = 0 ;
  192.    for( int j = 1 ; j <= q ; j++ )
  193.    {
  194.       long long l , r ;
  195.       l = 1 + ( a*ans + j*b)%n ;
  196.       r = l + ( c*ans + j*d )%(n-l+1);
  197.  
  198.  
  199.       ans = 1 ;
  200.  
  201.       for( int i = 0 ; i < counter ; i++ )
  202.       {
  203.  
  204.         int k = log_arr[r - l + 1];
  205.         //cout << k << "  " << i << endl ;
  206.         int mul = max( segtree[ i ][ k ][ l ]-'\0' , segtree[ i ][ k ][ r - twopower[ k ]+ 1 ]-'\0' );
  207.         ans = ( ans * primepower[ mul ][ i ])%mod ;
  208.       }
  209.  
  210.       ans = ( ans * query( 1 , n , root[r] , l , r ) )%mod ;
  211.       printf("%lld\n",ans );
  212.    }
  213.  
  214.  
  215.    return 0 ;
  216. }
Time limit exceeded #stdin #stdout 5s 214528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/loLaMW
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!