fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <iostream>
  5. #include <memory.h>
  6. #include <math.h>
  7. #include <assert.h>
  8. #include <queue>
  9. #include <deque>
  10. #include <map>
  11. #include <set>
  12. #include <cstring>
  13. #include <string>
  14. #include <algorithm>
  15. #include <functional>
  16. #include <vector>
  17. #include <stack>
  18. #include <unordered_map>
  19. #include <list>
  20. #include <time.h>
  21.  
  22. using namespace std;
  23.  
  24. typedef long long ll;
  25. typedef unsigned long long ull;
  26. typedef pair<int, int> Pi;
  27. typedef pair<ll, ll> Pll;
  28. typedef pair<ll, int> Pli;
  29. typedef pair<int, ll> Pil;
  30. typedef pair<double, int> Pdi;
  31. typedef tuple<int, int, int> Ti;
  32. typedef tuple<int, int, ll> Tiil;
  33. typedef tuple<ll, int, int> Tlii;
  34. typedef tuple<ll, ll, int> Tlli;
  35.  
  36. #define Fi first
  37. #define Se second
  38. #define pb push_back
  39. #define mp make_pair
  40. #define mt make_tuple
  41. #define rep(pos, len) for(int pos=0;pos<len;pos++)
  42. #define repp(pos, len) for(int pos=1;pos<=len;pos++)
  43. #define all(x) x.begin(), x.end()
  44.  
  45. #define ABS(x) (((x) > 0 ) ? (x) : (-(x)))
  46. #define MAX2(x, y) (((x) > (y)) ? (x) : (y))
  47. #define MIN2(x, y) (((x) < (y)) ? (x) : (y))
  48. #define MAX3(x, y, z) ( (x) > (y)  ? ( (x) > (z) ? (x) : (z)  ) : ( (y) > (z) ? (y) : (z) )  )
  49. #define MIN3(x, y, z) ( (x) < (y)  ? ( (x) < (z) ? (x) : (z)  ) : ( (y) < (z) ? (y) : (z) )  )
  50. #define MID3(val1,val2,val3) MAX2(MIN2(MAX2(val1,val2),val3),MIN2(val1,val2))
  51.  
  52. #define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
  53.  
  54. #define geti1(X) scanf("%d",&X)
  55. #define geti2(X,Y) scanf("%d%d",&X,&Y)
  56. #define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
  57. #define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)
  58. #define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)
  59.  
  60. #define getll1(X) scanf("%lld",&X)
  61. #define getll2(X,Y) scanf("%lld%lld",&X,&Y)
  62. #define getll3(X,Y,Z) scanf("%lld%lld%lld",&X,&Y,&Z)
  63. #define getll4(X,Y,Z,W) scanf("%lld%lld%lld%lld",&X,&Y,&Z,&W)
  64. #define getll(...) GET_MACRO(__VA_ARGS__, getll4, getll3, getll2, getll1) (__VA_ARGS__)
  65.  
  66. #define dout(n) printf("%d\n",n)
  67. #define lldout(n) printf("%lld\n",n)
  68.  
  69. // 1-index
  70. #define L(x) ((x)<<1)
  71. #define R(x) (((x)<<1)+1)
  72.  
  73. #define INF 987654321
  74. #define IINF 98765432198765432
  75. #define MOD 1000000007
  76.  
  77. const int MAXN = 1e5 + 50;
  78.  
  79. ll fact[MAXN], finv[MAXN];	// fact[n] = n!, finv[MAXN] = (n!)^(-1)
  80. bool vis[MAXN];
  81. vector<int> pfactor[MAXN];
  82.  
  83. ll inverse(ll a, ll m) {
  84.     ll m0 = m, t, q;
  85.     ll x0 = 0, x1 = 1;
  86.  
  87.     if (m == 1)
  88.       return 0;
  89.  
  90.     while (a > 1) {
  91.         // q is quotient
  92.         q = a / m;
  93.         t = m;
  94.  
  95.         // m is remainder now, process same as
  96.         // Euclid's algo
  97.         m = a % m, a = t;
  98.         t = x0;
  99.         x0 = x1 - q * x0;
  100.         x1 = t;
  101.     }
  102.  
  103.     // Make x1 positive
  104.     if (x1 < 0)
  105.        x1 += m0;
  106.     return x1;
  107. }
  108.  
  109.  
  110. ll c(int n, int k) {
  111. 	return (((fact[n] * finv[k]) % MOD) * finv[n-k]) % MOD;
  112. }
  113.  
  114.  
  115.  
  116. void findPrime() {
  117. 	for(int n = 2; n <= 1e5; n++) {
  118. 		if(vis[n]) continue;
  119. 		vis[n] = true;
  120. 		for(int k = 1; k * n <= 1e5; k++) {
  121. 			vis[k * n] = true;
  122. 			pfactor[k * n].pb(n);
  123. 		}
  124. 	}
  125. }
  126.  
  127. void init() {
  128. 	fact[0] = 1;
  129. 	repp(n, 1e5) fact[n] = (fact[n-1] * n) % MOD;
  130. 	finv[0] = 1;
  131. 	repp(n, 1e5) finv[n] = inverse(fact[n], MOD);
  132. }
  133.  
  134. int main() {
  135. 	init();
  136. 	findPrime();
  137.  
  138. 	int T;
  139. 	geti(T);
  140. 	while(T--) {
  141. 		int n, f;
  142. 		geti(n, f);
  143. 		ll ans = 0;
  144. 		for(int mask = 0; mask < (1 << pfactor[n].size()); mask++) {
  145. 			int cnt = 0;
  146. 			int tmp = n;
  147. 			rep(i, pfactor[n].size()) {
  148. 				if((mask >> i) & 1) {
  149. 					tmp /= pfactor[n][i];
  150. 					cnt++;
  151. 				}
  152. 			}
  153. 			if(cnt & 1) {
  154. 				ans = (ans - c(tmp - 1, f - 1) + MOD) % MOD;
  155. 			} else {
  156. 				ans = (ans + c(tmp - 1, f - 1)) % MOD;
  157. 			}
  158. 		}
  159.  
  160. 		printf("%lld\n", ans);
  161. 	}
  162. }
Success #stdin #stdout 0.04s 22272KB
comments (?)
stdin
copy 
40
37 15
48 10
16 5
25 23
32 20
24 4
46 19
16 13
1 1
37 22
44 29
24 6
27 10
39 16
28 13
5 4
31 22
9 2
30 26
23 16
16 12
43 5
29 1
20 5
40 12
18 14
22 15
29 2
3 2
6 3
45 28
42 34
43 32
10 10
12 8
10 8
4 1
17 17
16 7
8 7
stdout
copy 
796297179
361826943
1330
276
141120525
1572
884475620
455
1
567902525
532655639
33166
3124550
471286455
17383847
4
14307150
6
23751
170544
1365
111930
0
3750
675980455
2380
116280
28
2
9
353793174
95548245
280561348
1
330
36
0
1
4998
7
https://ideone.com/jcoVSl
language:
C++14 (clang 8.0)
created:
6 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!