fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define nl puts ("")
  5. #define sp printf ( " " )
  6. #define phl printf ( "hello\n" )
  7. #define ff first
  8. #define ss second
  9. #define POPCOUNT __builtin_popcountll
  10. #define RIGHTMOST __builtin_ctzll
  11. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  12. #define MP make_pair
  13. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  14. #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
  15. #define CLR(x,y) memset(x,y,sizeof(x))
  16. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  17. #define MIN(a,b) ((a)<(b)?(a):(b))
  18. #define MAX(a,b) ((a)>(b)?(a):(b))
  19. #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
  20. #define SQ(x) ((x)*(x))
  21. #define ABS(x) ((x)<0?-(x):(x))
  22. #define FABS(x) ((x)+eps<0?-(x):(x))
  23. #define ALL(x) (x).begin(),(x).end()
  24. #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
  25. #define SZ(x) ((vlong)(x).size())
  26. #define NORM(x) if(x>=mod)x-=mod;
  27.  
  28. using namespace std;
  29.  
  30. typedef long long vlong;
  31.  
  32. #define SIZE 100001
  33.  
  34. int bit[SIZE+10];
  35.  
  36. void bitClear( int n ) {
  37.     FOR(i,1,n+2) {
  38.         bit[i] = 0;
  39.     }
  40. }
  41. void bitInsert ( int from, int what ) {
  42.     from++; ///Handle 0
  43.  
  44.     for ( int i = from; i <= SIZE; i += i & (-i) ) {
  45.         bit[i] += what;
  46.     }
  47. }
  48.  
  49. int bitQuery ( int at ) {
  50.     at++; ///Handle 0
  51.  
  52.     int res = 0;
  53.     for ( int i = at; i > 0; i -= i & -i ) {
  54.         res += bit[i];
  55.     }
  56.     return res;
  57. }
  58.  
  59.  
  60.  
  61. int main () {
  62.  
  63.     int kase, cnt = 0;
  64.     scanf ( "%d", &kase );
  65.  
  66.     while ( kase-- ) {
  67.         int n, k;
  68.         scanf ( "%d %d", &n, &k );
  69.  
  70.         bitClear(k); ///Clear BIT
  71.  
  72.         vlong total = 0;
  73.         vlong res = 0;
  74.         ROF(i,1,n) {
  75.             total++; ///Total number of "c" available
  76.  
  77.             int x = ( i * i * i ) % k;
  78.             bitInsert( x, 1 ); ///Insert another "c"
  79.  
  80.             res += ( i / k ) * total; ///This many "a" segment can handle any "c"
  81.  
  82.  
  83.             int r = i % k;
  84.             int b = ( i * i ) % k;
  85.  
  86.             if ( r > 0 ) { ///These parts of "a" were not used
  87.  
  88.                 int from = 1 + b; ///c >= 1 + b
  89.                 int to = r + b; ///c <= r + b
  90.  
  91.                 if ( from >= k ) { ///In case both from and to exceed k
  92.                     from -= k;
  93.                     to -= k;
  94.                 }
  95.  
  96.                 int seg = 0;
  97.                 if ( to < k ) { ///Continuous
  98.                     seg = bitQuery(to);
  99.                     seg -= bitQuery(from-1);
  100.                 }
  101.                 else { ///Wraps around
  102.                     seg = bitQuery(k-1); ///from - end
  103.                     seg -= bitQuery(from-1);
  104.  
  105.                     seg += bitQuery(to%k); ///0 - to
  106.                 }
  107.                 res += seg;
  108.             }
  109.         }
  110.  
  111.         printf ( "Case %d: %lld\n", ++cnt, res );
  112.     }
  113.  
  114.     return 0;
  115. }
  116.  
Runtime error #stdin #stdout 0s 3800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iMBUmU
Blog UVa 12429 - Finding Magic Triplets
language:
C++14 (gcc 8.3)
created:
10 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!