fork(1) download
copy 
  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. const vlong inf = 2147383647;
  38. const double pi = 2 * acos ( 0.0 );
  39. const double eps = 1e-9;
  40.  
  41. /***********Template Ends Here***********/
  42. vector<int> prime;
  43. char stat[1000100];
  44.  
  45. ///Generate primes till n
  46. void sieve( int n ) {
  47.     prime.pb ( 2 );
  48.     int sqrtn = sqrt ( n );
  49.  
  50.     for ( int i = 3; i <= sqrtn; i += 2 ) {
  51.         if ( stat[i] == 0 ) {
  52.             for ( int j = i * i; j <= n; j += 2 * i ) stat[j] = 1;
  53.         }
  54.     }
  55.     for ( int i = 3; i <= n; i += 2 ) if ( stat[i] == 0 ) prime.pb ( i );
  56. }
  57.  
  58. ///Calculate phi(n)
  59. vlong calcPhi ( vlong n ) {
  60.     vlong res = n;
  61.     int sqrtn = sqrt ( n );
  62.     for ( int i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) {
  63.         if ( n % prime[i] == 0 ) {
  64.             while ( (n % prime[i]) == 0 ) {
  65.                 n /= prime[i];
  66.             }
  67.             res /= prime[i];
  68.             res *= prime[i] - 1;
  69.         }
  70.     }
  71.     if ( n != 1 ) {
  72.         res /= n;
  73.         res *= n - 1;
  74.     }
  75.  
  76.     return res;
  77. }
  78.  
  79. vector < vlong > ddd, phi;
  80.  
  81. int main () {
  82.     sieve ( 1000000 );
  83.  
  84.     int kase, cnt = 0;
  85.     scanf ( "%d", &kase );
  86.  
  87.     while ( kase-- ) {
  88.         vlong n, q;
  89.         scanf ( "%lld %lld", &n, &q );
  90.  
  91.         ///Find all divisors of n
  92.         ddd.clear();
  93.         int sqrtn = sqrt ( n ) + eps;
  94.         FOR(i,1,sqrtn) {
  95.             if ( ( n % i ) == 0 ) {
  96.                 ddd.pb ( i );
  97.                 if ( n / i != i ) ddd.pb ( n / i );
  98.             }
  99.         }
  100.  
  101.         sort ( ALL(ddd) );
  102.  
  103.         phi.clear();
  104.         FOR(i,0,SZ(ddd)-1){
  105.             phi.pb ( calcPhi( n / ddd[i] ) );
  106.             if ( i ) phi[i] += phi[i-1]; ///Make it cumulative array of phi value
  107.         }
  108.  
  109.         printf ( "Case %d\n", ++cnt );
  110.         while ( q-- ) {
  111.             vlong x;
  112.             scanf ( "%lld", &x );
  113.  
  114.             if ( x >= n ) { ///All
  115.                 printf ( "%lld\n", n );
  116.                 continue;
  117.             }
  118.             if ( x < 1 ) { ///None
  119.                 printf ( "%lld\n", 0 );
  120.                 continue;
  121.             }
  122.  
  123.             int pos = upper_bound ( ALL(ddd), x ) - ddd.begin();
  124.  
  125.             pos--;
  126.  
  127.             printf ( "%lld\n", phi[pos] );
  128.         }
  129.     }
  130.  
  131.     return 0;
  132. }
  133.  
Time limit exceeded #stdin #stdout 5s 4952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WrIH0C
Blog UVa 12425 - Best Friend
language:
C++14 (gcc 8.3)
created:
9 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!