Guest User

Untitled

a guest
Aug 17th, 2016
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.33 KB | None | 0 0
  1. /*
  2. */
  3. #define _CRT_SECURE_NO_WARNINGS
  4.  
  5. //#pragma comment(linker, "/STACK:16777216")
  6. #include <fstream>
  7. #include <iostream>
  8. #include <string>
  9. #include <complex>
  10. #include <math.h>
  11. #include <set>
  12. #include <vector>
  13. #include <map>
  14. #include <queue>
  15. #include <stdio.h>
  16. #include <stack>
  17. #include <algorithm>
  18. #include <list>
  19. #include <ctime>
  20. #include <memory.h>
  21. #include <ctime>
  22. #include <assert.h>
  23.  
  24. #define y0 sdkfaslhagaklsldk
  25. #define y1 aasdfasdfasdf
  26. #define yn askfhwqriuperikldjk
  27. #define j1 assdgsdgasghsf
  28. #define tm sdfjahlfasfh
  29. #define lr asgasgash
  30.  
  31. #define eps 1e-8
  32. #define M_PI 3.141592653589793
  33. #define bs 998244353
  34. #define bsize 512
  35.  
  36. const int N = 1200000;
  37.  
  38. using namespace std;
  39.  
  40. int gcd(int a, int b)
  41. {
  42. while (a&&b)a > b ? a %= b : b %= a;
  43. return a + b;
  44. }
  45.  
  46. int lcm(int a, int b)
  47. {
  48. return a / gcd(a, b)*b;
  49. }
  50.  
  51. int pr[N];
  52. int tp[N];
  53.  
  54. int count_primes(int x)
  55. {
  56. return tp[x];
  57. }
  58.  
  59. long long TOTAL[1 << 20];
  60. long long SUM[1 << 20];
  61. long long pairs[1 << 20], ans[1 << 20];
  62.  
  63. int main(){
  64. //freopen("beavers.in","r",stdin);
  65. //freopen("beavers.out","w",stdout);
  66. //freopen("F:/in.txt","r",stdin);
  67. //freopen("F:/output.txt","w",stdout);
  68. //ios_base::sync_with_stdio(0);
  69. //cin.tie(0);
  70.  
  71.  
  72. pr[1] = 1;
  73. for (int i = 2; i <= 1000000; i++)
  74. {
  75. if (pr[i] == 0)
  76. {
  77. for (int j = i; j <= 1000000; j += i)
  78. pr[j] = 1,
  79. tp[j]++;
  80. }
  81. }
  82. pr[1] = 1;
  83. for (int i = 1; i <= 1000000; i++)
  84. {
  85. int V = 0;
  86. for (int j = i; j <= 1000000; j += i)
  87. {
  88. V++;
  89. int S = j + i;
  90. int ways = (1 << count_primes(V));
  91. if (S < (1 << 20))
  92. TOTAL[S] += ways;
  93. }
  94. }
  95.  
  96. /*for (int i = 1; i <= 10; i++)
  97. {
  98. cout << TOTAL[i] << endl;
  99. }
  100. */
  101.  
  102. for (int i = 1; i <= 1000000; i++)
  103. {
  104. SUM[i] = SUM[i - 1] + TOTAL[i] * i;
  105. TOTAL[i] += TOTAL[i - 1];
  106. }
  107.  
  108. for (int i = 1; i <= 1000000; i++)
  109. {
  110. ans[i] = ans[i - 1] + pairs[i - 1]+2*i-1;
  111. pairs[i] = pairs[i - 1] + 2 * i - 1;
  112. ans[i] %= bs;
  113. pairs[i] %= bs;
  114. }
  115.  
  116. int tests;
  117.  
  118. cin >> tests;
  119. //tests = 100000;
  120.  
  121. for (; tests; --tests)
  122. {
  123. int n;
  124. // cin >> n;
  125. scanf("%d", &n);
  126. //n = 1000000;
  127.  
  128. long long res = ans[n];
  129. res -= TOTAL[n] * n%bs;
  130. if (res < 0)
  131. res += bs;
  132. res += SUM[n];
  133. res %= bs;
  134. //cout << res << "\n";
  135. int here = res;
  136. printf("%d\n", here);
  137. }
  138.  
  139. cin.get();cin.get();
  140. return 0;
  141. }
Advertisement
Add Comment
Please, Sign In to add comment