結果

問題 No.1760 Setwise Coprime
コンテスト
ユーザー 👑 希丝缇娜菲贝尔
提出日時 2026-08-29 16:14:23
言語 cLay
(20250308-1 + boost 1.92.0)
コンパイル:
clayc _filename_
実行:
./a.out
結果
AC  
実行時間 45 ms / 2,000 ms
+ 541µs
コード長 1,084 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,929 ms
コンパイル使用メモリ 194,700 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2026-08-29 16:14:33
合計ジャッジ時間 5,182 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define MD 998244353
using mm = Mint;
const int MAXN = 2d5 + 5;

int mu[MAXN], lp[MAXN], p[MAXN], pc;
mm pw2[MAXN * 2], pw3[MAXN];

{
	int @N;

	mu[1] = 1;
	rep(i, 2, N + 1) {
		if(!lp[i]) lp[i] = i, p[pc ++] = i, mu[i] = -1;
		rep(j, pc) {
			int q = p[j];
			if(i * q > N) break;
			lp[i * q] = q;
			if(i % q == 0) {mu[i * q] = 0; break;}
			mu[i * q] = -mu[i];
		}
	}

	pw2[0] = 1;
	rep(i, 1, 2 * N + 1) pw2[i] = pw2[i - 1] * 2;
	pw3[0] = 1;
	rep(i, 1, N + 1) pw3[i] = pw3[i - 1] * 3;

	mm C = 0;
	rep(d, 1 , N + 1) C += mu[d] * (pw2[N / d] - 1);
	mm ans = C * C;

	rep(L, 1, N + 1) {
		if(mu[L] == 0) continue;

		int fac[10], k = 0, x = L;
		while(x > 1) fac[k ++] = lp[x], x /= lp[x];

		int limit = 1; rep(i, k) limit *= 3;

		int z = N / L;

		rep(bit, limit) {
			int d = 1, e = 1, t = bit;

			rep(i, k) {
				int s = t % 3; t /= 3;
				if(s == 0) d *= fac[i];
				else if(s == 1) e *= fac[i];
				else d *= fac[i], e *= fac[i];
			}

			int a = N / d, b = N / e;

			mm delta = pw2[a + b - 2 * z] * pw3[z] - pw2[a + b];
			ans += mu[d] * mu[e] * delta;
		}

	}
	wt(ans);
}
0