fork download 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
  6. template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
  7. const int MAXN = (1 << 20);
  8. const int mod = (int)1e9 + 7;
  9.  
  10. int64_t n;
  11.  
  12. void read()
  13. {
  14. 	cin >> n;
  15. }
  16.  
  17. vector<int> li;
  18. int a[MAXN];
  19.  
  20. int pw(int x, int64_t p)
  21. {
  22. 	int ret = 1;
  23. 	while(p)
  24. 	{
  25. 		if(p & 1ll) ret = (ret * 1ll * x) % mod;
  26. 		p >>= 1ll;
  27. 		x = (x * 1ll * x) % mod;
  28. 	}
  29.  
  30. 	return ret;
  31. }
  32.  
  33. int64_t cnt[MAXN];
  34.  
  35. void solve()
  36. {
  37. 	vector<int64_t> li;
  38. 	for(int64_t d = 1; d * 1ll * d <= n; d++)
  39. 		if(n % d == 0)
  40. 		{
  41. 			li.push_back(d);
  42. 			li.push_back(n / d);
  43. 		}
  44.  
  45. 	sort(li.begin(), li.end());
  46. 	li.erase(unique(li.begin(), li.end()), li.end());
  47.  
  48. 	memset(cnt, 0, sizeof(cnt));
  49.  
  50. 	int64_t answer = n % mod;
  51. 	int po = 0;
  52. 	for(int64_t l: li)
  53. 	{
  54. 		po++;
  55. 		if(l == 1 || l == n) continue;
  56. 		int64_t p = ((n / l - 1) % mod);
  57. 		cnt[po - 1] = (pw(2, l) + mod - 2ll) % mod;
  58.  
  59. 		for(int i = po - 2; i >= 0; i--)
  60. 			if(l % li[i] == 0) 
  61. 				cnt[po - 1] = (cnt[po - 1] - cnt[i] + mod) % mod;
  62.  
  63. 		p = (p * 1ll * cnt[po - 1]) % mod;
  64. 		answer = (answer + p) % mod;
  65. 	}
  66.  
  67. 	cout << answer << endl;
  68. }
  69.  
  70. int main()
  71. {
  72. 	freopen("gymnasts.in", "r", stdin);
  73. 	freopen("gymnasts.out", "w", stdout);
  74. 	ios_base::sync_with_stdio(false);
  75. 	cin.tie(NULL);
  76.  
  77. 	read();
  78. 	solve();
  79. 	return 0;
  80. }
  81.  
  82.  
Runtime error #stdin #stdout #stderr 0s 4512KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/wMsA7P
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!