fork download 
  1. /***********Template Starts Here***********/
  2. #include <bits/stdc++.h>
  3.  
  4. #define pb push_back
  5. #define nl puts ("")
  6. #define sp printf ( " " )
  7. #define phl printf ( "hello\n" )
  8. #define ff first
  9. #define ss second
  10. #define POPCOUNT __builtin_popcountll
  11. #define RIGHTMOST __builtin_ctzll
  12. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  13. #define MP make_pair
  14. #define FOR(i,x,y) for(int i = (x) ; i <= (y) ; ++i)
  15. #define ROF(i,x,y) for(int i = (y) ; i >= (x) ; --i)
  16. #define CLR(x,y) memset(x,y,sizeof(x))
  17. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  18. #define MIN(a,b) ((a)<(b)?(a):(b))
  19. #define MAX(a,b) ((a)>(b)?(a):(b))
  20. #define NUMDIGIT(x,y) (((int)(log10((x))/log10((y))))+1)
  21. #define SQ(x) ((x)*(x))
  22. #define ABS(x) ((x)<0?-(x):(x))
  23. #define FABS(x) ((x)+eps<0?-(x):(x))
  24. #define ALL(x) (x).begin(),(x).end()
  25. #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
  26. #define SZ(x) ((int)(x).size())
  27.  
  28. using namespace std;
  29.  
  30. typedef long long vlong;
  31. typedef unsigned long long uvlong;
  32. typedef pair < int, int > pii;
  33. typedef pair < vlong, vlong > pll;
  34. typedef vector<pii> vii;
  35. typedef vector<int> vi;
  36.  
  37. /***********Template Ends Here***********/
  38. vlong b, m;
  39.  
  40. ///find (a*b)%m without overflowing
  41. vlong mulMod ( vlong a, vlong b ) {
  42.     vlong res = 0;
  43.     vlong x = a;
  44.     while ( b ) {
  45.         if ( b & 1 ) {
  46.             res = res + x;
  47.             if ( res >= m ) res -= m;
  48.         }
  49.         x = ( x + x );
  50.         if ( x >= m ) x -= m;
  51.         b >>= 1;
  52.     }
  53.  
  54.     return res;
  55. }
  56.  
  57. vlong bigmodExtended ( vlong a, vlong p ) {
  58.     vlong res = 1 % m, x = a % m;
  59.     while ( p ) {
  60.         if ( p & 1 ) res = mulMod( res, x );
  61.         x = mulMod( x , x ); p >>= 1;
  62.     }
  63.     return res;
  64. }
  65.  
  66. vlong divMod ( vlong n ) {
  67.     if ( n == 1 ) {
  68.         return 1 % m;
  69.     }
  70.  
  71.     if ( n & 1 ) {
  72.         vlong res = bigmodExtended( b, n-1 ) + divMod( n - 1 );
  73.         if ( res >= m ) res -= m;
  74.  
  75.         return res;
  76.     }
  77.     else {
  78.         vlong res = divMod(n/2);
  79.         vlong temp = 1 + bigmodExtended(b,n/2);
  80.         if ( temp >= m ) temp -= m;
  81.  
  82.         if ( temp == 0 || res == 0 ) return 0;
  83.         return mulMod ( res, temp );
  84.     }
  85. }
  86.  
  87. int main () {
  88.     int kase, cnt = 0;
  89.     scanf ( "%d", &kase );
  90.  
  91.     while ( kase-- ) {
  92.         vlong n, d;
  93.         scanf ( "%lld %lld %lld %lld", &n, &b, &d, &m );
  94.  
  95.         vlong res = divMod ( n );
  96.  
  97.         res = ( res * d );
  98.         res %= m;
  99.  
  100.         printf ( "Case %d: %lld\n", ++cnt, res );
  101.     }
  102.  
  103.     return 0;
  104. }
  105.  
Runtime error #stdin #stdout 0s 3456KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Fn6vzW
Blog UVa 12431 - Happy 10/9 Day
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!