Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- */
- #define _CRT_SECURE_NO_WARNINGS
- //#pragma comment(linker, "/STACK:16777216")
- #include <fstream>
- #include <iostream>
- #include <string>
- #include <complex>
- #include <math.h>
- #include <set>
- #include <vector>
- #include <map>
- #include <queue>
- #include <stdio.h>
- #include <stack>
- #include <algorithm>
- #include <list>
- #include <ctime>
- #include <memory.h>
- #include <ctime>
- #include <assert.h>
- #define y0 sdkfaslhagaklsldk
- #define y1 aasdfasdfasdf
- #define yn askfhwqriuperikldjk
- #define j1 assdgsdgasghsf
- #define tm sdfjahlfasfh
- #define lr asgasgash
- #define eps 1e-8
- #define M_PI 3.141592653589793
- #define bs 998244353
- #define bsize 512
- const int N = 1200000;
- using namespace std;
- int gcd(int a, int b)
- {
- while (a&&b)a > b ? a %= b : b %= a;
- return a + b;
- }
- int lcm(int a, int b)
- {
- return a / gcd(a, b)*b;
- }
- int pr[N];
- int tp[N];
- int count_primes(int x)
- {
- return tp[x];
- }
- long long TOTAL[1 << 20];
- long long SUM[1 << 20];
- long long pairs[1 << 20], ans[1 << 20];
- int main(){
- //freopen("beavers.in","r",stdin);
- //freopen("beavers.out","w",stdout);
- //freopen("F:/in.txt","r",stdin);
- //freopen("F:/output.txt","w",stdout);
- //ios_base::sync_with_stdio(0);
- //cin.tie(0);
- pr[1] = 1;
- for (int i = 2; i <= 1000000; i++)
- {
- if (pr[i] == 0)
- {
- for (int j = i; j <= 1000000; j += i)
- pr[j] = 1,
- tp[j]++;
- }
- }
- pr[1] = 1;
- for (int i = 1; i <= 1000000; i++)
- {
- int V = 0;
- for (int j = i; j <= 1000000; j += i)
- {
- V++;
- int S = j + i;
- int ways = (1 << count_primes(V));
- if (S < (1 << 20))
- TOTAL[S] += ways;
- }
- }
- /*for (int i = 1; i <= 10; i++)
- {
- cout << TOTAL[i] << endl;
- }
- */
- for (int i = 1; i <= 1000000; i++)
- {
- SUM[i] = SUM[i - 1] + TOTAL[i] * i;
- TOTAL[i] += TOTAL[i - 1];
- }
- for (int i = 1; i <= 1000000; i++)
- {
- ans[i] = ans[i - 1] + pairs[i - 1]+2*i-1;
- pairs[i] = pairs[i - 1] + 2 * i - 1;
- ans[i] %= bs;
- pairs[i] %= bs;
- }
- int tests;
- cin >> tests;
- //tests = 100000;
- for (; tests; --tests)
- {
- int n;
- // cin >> n;
- scanf("%d", &n);
- //n = 1000000;
- long long res = ans[n];
- res -= TOTAL[n] * n%bs;
- if (res < 0)
- res += bs;
- res += SUM[n];
- res %= bs;
- //cout << res << "\n";
- int here = res;
- printf("%d\n", here);
- }
- cin.get();cin.get();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment