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