結果
| 問題 | No.1760 Setwise Coprime |
| ユーザー |
 heno239
|
| 提出日時 | 2021-11-20 16:19:18 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 479 ms / 2,000 ms |
| コード長 | 6,921 bytes |
| コンパイル時間 | 2,415 ms |
| コンパイル使用メモリ | 160,908 KB |
| 最終ジャッジ日時 | 2025-01-25 21:53:46 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include<iostream>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<bitset>#include<stack>#include<unordered_map>#include<unordered_set>#include<utility>#include<cassert>#include<complex>#include<numeric>#include<array>#include<chrono>using namespace std;//#define int long longtypedef long long ll;typedef unsigned long long ul;typedef unsigned int ui;const ll mod = 998244353;const ll INF = mod * mod;typedef pair<int, int>P;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)#define all(v) (v).begin(),(v).end()typedef pair<ll, ll> LP;typedef double ld;typedef pair<ld, ld> LDP;const ld eps = 1e-4;const ld pi = acosl(-1.0);template<typename T>void chmin(T& a, T b) {a = min(a, b);}template<typename T>void chmax(T& a, T b) {a = max(a, b);}ll mod_pow(ll x, ll n, ll m = mod) {if (n < 0) {ll res = mod_pow(x, -n, m);return mod_pow(res, m - 2, m);}if (abs(x) >= m)x %= m;if (x < 0)x += m;ll res = 1;while (n) {if (n & 1)res = res * x % m;x = x * x % m; n >>= 1;}return res;}struct modint {ll n;modint() :n(0) { ; }modint(ll m) :n(m) {if (n >= mod)n %= mod;else if (n < 0)n = (n % mod + mod) % mod;}operator int() { return n; }};bool operator==(modint a, modint b) { return a.n == b.n; }modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }modint operator+(modint a, modint b) { return a += b; }modint operator-(modint a, modint b) { return a -= b; }modint operator*(modint a, modint b) { return a *= b; }modint operator^(modint a, ll n) {if (n == 0)return modint(1);modint res = (a * a) ^ (n / 2);if (n % 2)res = res * a;return res;}ll inv(ll a, ll p) {return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);}modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }modint operator/=(modint& a, modint b) { a = a / b; return a; }const int max_n = 1 << 20;modint fact[max_n], factinv[max_n];void init_f() {fact[0] = modint(1);for (int i = 0; i < max_n - 1; i++) {fact[i + 1] = fact[i] * modint(i + 1);}factinv[max_n - 1] = modint(1) / fact[max_n - 1];for (int i = max_n - 2; i >= 0; i--) {factinv[i] = factinv[i + 1] * modint(i + 1);}}modint comb(int a, int b) {if (a < 0 || b < 0 || a < b)return 0;return fact[a] * factinv[b] * factinv[a - b];}modint combP(int a, int b) {if (a < 0 || b < 0 || a < b)return 0;return fact[a] * factinv[a - b];}int dx[4] = { 1,0,-1,0 };int dy[4] = { 0,1,0,-1 };ll gcd(ll a, ll b) {a = abs(a);b = abs(b);if (a < b)swap(a, b);while (b) {ll r = a % b; a = b; b = r;}return a;}template <typename T>void fwt(vector<T>& f) {int n = f.size();for (int i = 1; i < n; i <<= 1) {for (int j = 0; j < n; j++) {if ((j & i) == 0) {T x = f[j], y = f[j | i];f[j] = x + y, f[j | i] = x - y;}}}}template <typename T>void ifwt(vector<T>& f) {int n = f.size();for (int i = 1; i < n; i <<= 1) {for (int j = 0; j < n; j++) {if ((j & i) == 0) {T x = f[j], y = f[j | i];f[j] = (x + y) / 2, f[j | i] = (x - y) / 2;}}}}typedef vector<vector<modint>> mat;typedef vector<modint> vec;mat mtmul(mat& A, mat& B) {mat C(A.size(), vec(B[0].size()));rep(i, (int)A.size()) {rep(k, (int)B.size()) {rep(j, (int)B[0].size()) {C[i][j] += A[i][k] * B[k][j];}}}return C;}mat mtpow(mat A, ll n) {mat B(A.size(), vec(A.size()));rep(i, (int)A.size()) {B[i][i] = 1;}while (n > 0) {if (n & (ll)1)B = mtmul(B, A);A = mtmul(A, A);n >>= 1;}return B;}const int mn = 200005;bool isp[mn];vector<int> ch[mn];int meb[mn];void init() {fill(isp + 2, isp + mn, true);fill(meb + 1, meb + mn, 1);for (int i = 2; i < mn; i++) {if (!isp[i])continue;meb[i] *= -1;for (int j = 2 * i; j < mn; j+=i) {isp[j] = false;meb[j] *= -1;if ((j / i) % i == 0)meb[j] = 0;}}//rep(i, 20)cout << i << " " << meb[i] << "\n";for (int i = 1; i < mn; i++) {if (meb[i] != 0) {for (int j = i; j < mn; j += i) {ch[j].push_back(i);}}}}void solve() {int n; cin >> n;vector<modint> t2(n + 1), t3(n + 1);t2[0] = 1;t3[0] = 1;rep(i, n) {t2[i + 1] = t2[i] + t2[i];t3[i + 1] = (modint)3 * t3[i];}modint presum = 0;vector<modint> mem(n + 1);rep1(i, n)mem[i]= (modint)meb[i] * t2[n / i];rep1(i, n)presum += mem[i];vector<modint> sum(n + 1,presum);/*int premebsum = 0;rep1(i, n)premebsum += meb[i];vector<int> mebsum(n + 1,premebsum);*/int cnt[2] = {};rep1(i, n) {if (meb[i] == 1)cnt[1]++;else if (meb[i] == -1)cnt[0]++;}modint ans = 0;/*rep1(i, n)rep1(j, n) {int g = gcd(i, j);int l = i / g * j;modint val = meb[i] * meb[j];modint num= t3[n / l] * t2[n / i - n / l] * t2[n / j - n / l];//num -= t2[n / i];//num -= t2[n / j];//num += 1;val *= num;ans += val;}*///cout << ans << "\n"; ans = 0;for (int l = 1; l <= n; l++) {rep(i, ch[l].size()) {Rep(j, i, ch[l].size()) {int c1 = ch[l][i];int c2 = ch[l][j];int g = gcd(c1, c2);if ((ll)(c1/g)*c2== l) {sum[c1] -= mem[c2]; //mebsum[c1] -= meb[c2];if (c1 != c2)sum[c2] -= mem[c1]; //mebsum[c2] -= meb[c1];modint val = meb[c1] * meb[c2];if (c1 != c2)val = val + val;val *= t3[n / l] * t2[n / c1 - n / l] * t2[n / c2 - n / l];ans += val;//cout << "? " << l << " " << c1 << " " << c2 << " " << val << "\n";}}}}//cout << cnt[1] - cnt[0] << "\n";for (int i = 1; i <= n; i++) {if (meb[i] == 0)continue;//cout << i << " " << sum[i] << "\n";modint val = mem[i] * sum[i];//cout << "? " << i << " " << val << "\n";ans += val;val = mem[i];modint coef = cnt[1] - cnt[0];ans -= val * coef;ans -= (modint)meb[i] * presum;/*rep1(j, n) {val =(modint)( meb[i] * meb[j]) * t2[n / i];ans -= val;ans += meb[i] * meb[j];}*/}ll c1 = (ll)cnt[1] * cnt[1] + (ll)cnt[0] * cnt[0];ll c2 = (ll)2 * cnt[0] * cnt[1];ans += c1 - c2;/*cout << c1 - c2 << "\n";int r = 0;rep1(i, n)rep1(j, n) {r += meb[i] * meb[j];}cout << r << "\n";*/cout << ans << "\n";}signed main() {ios::sync_with_stdio(false);cin.tie(0);//cout << fixed << setprecision(10);//init_f();init();//int t; cin >> t; rep(i, t)solve();return 0;}