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. 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
stdin
Standard input is empty
stdout
Standard output is empty