QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#682704#8327. 积性函数求和 $10^{13}$ 方便 FFT 版zydyAC ✓5894ms141568kbC++179.6kb2024-10-27 17:02:032024-10-27 17:02:03

Judging History

你现在查看的是最新测评结果

  • [2024-10-27 17:02:03]
  • 评测
  • 测评结果:AC
  • 用时:5894ms
  • 内存:141568kb
  • [2024-10-27 17:02:03]
  • 提交

answer

#include <iostream>
#include <vector>
#include <cmath>
#include <functional>
#include <algorithm>
#include <time.h>
#include <fstream>
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using i64 = long long;
constexpr u32 mod = 469762049;
inline constexpr u32 norm(const u32 x) { return x < mod ? x : x - mod; }
struct m32 {
	u32 x;
	m32() { }
	constexpr m32(const u32 _x) : x(_x) { }
};
inline constexpr m32 operator + (const m32 x1, const m32 x2) { return norm(x1.x + x2.x); }
inline constexpr m32 operator - (const m32 x1, const m32 x2) { return norm(x1.x + mod - x2.x); }
inline constexpr m32 operator - (const m32 x) { return x.x ? mod - x.x : 0; }
inline constexpr m32 operator * (const m32 x1, const m32 x2) { return static_cast<u64>(x1.x) * x2.x % mod; }
inline m32& operator += (m32& x1, const m32 x2) { return x1 = x1 + x2; }
inline m32& operator -= (m32& x1, const m32 x2) { return x1 = x1 - x2; }
inline m32& operator *= (m32& x1, const m32 x2) { return x1 = x1 * x2; }
inline bool operator == (const m32 x1, const m32 x2) { return x1.x == x2.x; }
inline bool operator != (const m32 x1, const m32 x2) { return x1.x != x2.x; }

struct block {
	static int v;
	vector<m32> sv;
	vector<m32> lv;
	block() : sv(v + 1, 0), lv(v + 1, 0) {}
};
int block::v;

inline void add(m32& x, const u32 a, const u32 b) { x = (x.x + 1ULL * a * b) % mod; }
inline void add(m32& x, const m32 a, const m32 b) { add(x, a.x, b.x); }
inline void sub(m32& x, const m32 a, const m32 b) { add(x, a.x, mod - b.x); }

block solve(const i64 N, m32 A, m32 B) {
	const int v = sqrt(N + 0.5);
	const int n_4 = sqrt(v + 0.5);
	const int n_8 = sqrt(n_4 + 0.5);
	block::v = v;

	vector<int> primes;
	vector<int> pi(v + 1);
	vector<bool> is_prime(v + 1);
	primes.push_back(1);
	is_prime[2] = true;
	for (int i = 3; i <= v; i += 2) is_prime[i] = true;
	for (int i = 3; i * i <= v; i += 2)
		for (int j = i * i; is_prime[i] && j <= v; j += (i << 1))
			is_prime[j] = false;
	for (int i = 2; i <= v; ++i) {
		pi[i] = pi[i - 1] + is_prime[i];
		if (is_prime[i]) primes.push_back(i);
	}

	vector<m32> sup;
	sup.resize(primes.size());
	u32 rec[4];
	rec[1] = 1;
	for (int i = 2; i <= 3; ++i)
		rec[i] = (i64)(mod - mod / i) * rec[mod % i] % mod;
	m32 inv3 = m32(rec[3]);

	const auto divide = [](i64 n, i64 d) -> i64 {return double(n) / d; };
	const auto divide_32 = [](i64 n, int d) -> int {return double(n) / d; };

	auto calc_medium = [&](const function<m32(u64)>& fp) {
		sup.clear();
		sup[0] = m32(0);
		for (int i = 1; i <= pi[v]; ++i) sup[i] = fp(primes[i]);

		vector<m32> lq(v + 1, 0);
		for (int i = 1; i <= pi[v]; ++i) lq[primes[i]] += sup[i];
		for (int i = 1; i <= v; ++i) lq[i] += lq[i - 1];

		block f;
		const i64 K1 = max<i64>(min((i64)pow(N, 2.0 / 3) * 4, N), v + 1);
		const int _v = sqrt(K1), B1 = N / K1;
		for (int i = pi[n_4] + 1; i <= pi[_v]; ++i) {
			const i64 M = N / primes[i];
			const int t = pi[min(divide_32(K1, primes[i]), v)];
			for (int j = i; j <= t; ++j) f.lv[divide_32(M, primes[j])] += sup[i] * sup[j];
		}
		for (int i = v - 1; i > B1; --i) f.lv[i] += f.lv[i + 1];
		for (int k = 1; k <= B1; ++k) {
			f.lv[k] = m32(0);
			const i64 M = N / k;
			const int t1 = pi[sqrt(M + 0.5)], t0 = pi[v / k];
			int j = pi[n_4] + 1;
			for (; j <= t0; ++j) f.lv[k] += sup[j] * (lq[v] - lq[primes[j - 1]]);
			for (; j <= t1; ++j) f.lv[k] += sup[j] * (lq[divide_32(M, primes[j])] - lq[primes[j - 1]]);
		}
		for (int k = 1; k <= n_4; ++k) {
			int t = v / k;
			i64 m = N / k;
			m32 ans = m32(0);
			for (int i = pi[n_4] + 1; i <= pi[t]; ++i) ans += sup[i] * f.lv[primes[i] * k];
			for (int i = pi[n_4] + 1; i <= pi[t]; ++i) {
				i64 q = (i64)primes[i] * primes[i];
				if (q * n_4 > m) break;
				ans += sup[i] * sup[i] * (lq[divide(m, q)] - lq[n_4]);
			}
			t = cbrt(m + 0.5);
			for (int i = pi[n_4] + 1; i <= pi[t]; ++i) ans += sup[i] * sup[i] * sup[i];
			f.lv[k] += ans * inv3;
		}
		for (int i = 1; i <= v; ++i) f.lv[i] += lq[v] - lq[n_4] + 1;
		for (int i = 1; i <= n_4; ++i) f.sv[i] = 1;
		for (int i = n_4 + 1; i <= v; ++i) f.sv[i] = lq[i] - lq[n_4] + 1;
		for (int i = 0; i <= v; ++i) lq[i] = 0;

		vector<m32> sq(v + 1, 0);
		int mm = v * max(log(N) / 10, 1.);
		int K = min(N, (i64)(mm * pow(N, 0.125))), B = N / K;
		m32 sum_s = 0;
		const auto add_s = [&](int x, m32 cnt) -> void {
			sum_s += cnt;
			while (x <= v) sq[x] += cnt, x += x & -x;
			};
		const auto add_l = [&](int x, m32 cnt) -> void {
			x = v + 1 - x;
			while (x <= v) lq[x] += cnt, x += x & -x;
			};
		function <void(int, int, m32)> dfs = [&](int n, int id, m32 fn) {
			if (n <= v) add_s(n, fn);
			else add_l(divide_32(N, n), fn);
			for (int i = id; i <= pi[v]; ++i) {
				i64 q = (i64)n * primes[i];
				if (q > K) break;
				dfs(q, i, fn * sup[i]);
			}
			};
		auto query_s = [&](int x) -> m32 {
			m32 ans = f.sv[x];
			while (x) ans += sq[x], x ^= x & -x;
			return ans;
			};
		auto query_l = [&](int x) -> m32 {
			x = v + 1 - x;
			m32 ans = sum_s;
			while (x) ans += lq[x], x ^= x & -x;
			return ans;
			};
		int K2, B2;
		for (int id = pi[n_4]; id > pi[n_8]; --id) {
			const int p = primes[id];
			const u64 m = N / p;
			dfs(p, id, sup[id]);
			const int t0 = B / p, t1 = min(B, v / p);
			for (int i = B; i > t1; --i) add(f.lv[i], sup[id], query_s(divide_32(m, i)));
			for (int i = t1; i > t0; --i) add(f.lv[i], sup[id], f.lv[i * p] + query_l(i * p));
			for (int i = t0; i; --i) add(f.lv[i], sup[id], f.lv[i * p]);
			K2 = mm * sqrt(p);
			B2 = N / K2;
			for (int i = B2; i > B; --i) f.lv[i] += query_l(i);
			K = K2, B = B2;
		}
		for (int i = B + 1; i <= v; ++i) f.lv[i] += query_l(i);
		for (int i = 1; i <= v; ++i)
			if (i & (i - 1))
				sq[i] += sq[i & (i - 1)];
		for (int i = 1; i <= v; ++i) f.sv[i] += sq[i];
		return f;
		};

	auto attach_small = [&](block&& f, const function<m32(u64)>& fp) {
		for (int id = pi[n_8]; id; --id) {
			const int p = primes[id], t = v / p;
			const i64 m = N / p;
			for (int j = 1, i = p; j <= t; ++j) {
				const m32 c1 = sup[id] * f.sv[j];
				for (int e = min(v + 1, i + p); i < e; ++i) f.sv[i] += c1;
			}
			for (int i = v; i > t; --i) add(f.lv[i], sup[id], f.sv[divide_32(m, i)]);
			for (int i = t; i >= 1; --i) add(f.lv[i], sup[id], f.lv[i * p]);
		}
		return move(f);
		};

	auto calc_large = [&](const function<m32(u64)>& fp, const function<m32(u64)>& sum_fp) {
		block f = attach_small(calc_medium(fp), fp);
		block res;
		for (int i = v; i >= 1; --i) {
			m32 ans = sum_fp(N / i) - f.lv[i];
			for (int j = 2; i * j <= v; ++j) sub(ans, fp(j), res.lv[i * j]);
			res.lv[i] = ans;
		}
		return res;
		};

	auto mult_large = [&](block&& f, const block& l) {
		for (int i = 1; i <= v; ++i) {
			for (int j = 1; i * j <= v; ++j)
				if (f.sv[j] != f.sv[j - 1])
					add(f.lv[i], f.sv[j] - f.sv[j - 1], l.lv[i * j]);
		}
		return move(f);
		};

	auto mult_powerful = [&](block&& f, const function<m32(u32, u32)>& fpp) {
		block h;
		function< void(u64, int, m32)> dfs = [&](u64 n, int beg, m32 coeff) -> void {
			if (n <= v) h.sv[n] += coeff;
			else h.lv[divide(N, n)] += coeff;
			u64 t = divide(N, n);
			for (int i = beg; i <= pi[v]; ++i) {
				const int p = primes[i];
				u64 q = 1ULL * p * p;
				if (q > t) break;
				for (int e = 2; q <= t; q *= p, ++e)
					dfs(n * q, i + 1, coeff * (fpp(p, e) - fpp(p, 1) * fpp(p, e - 1)));
			}
			};
		dfs(1, 1, 1);

		block res;
		for (int i = 1; i <= v; ++i)
			if (h.sv[i].x) {
				const i64 m = divide(N, i);
				const int t0 = sqrt(m + 0.5);
				for (int k = 1; k * i <= v; ++k)
					add(res.lv[k], h.sv[i], f.sv[v] - f.sv[t0]);
				for (int k = v / i + 1; k <= t0; ++k)
					add(res.lv[k], h.sv[i], f.sv[divide_32(m, k)] - f.sv[t0]);
			}
		for (int i = 1; i < v; ++i) res.lv[i] -= res.lv[i + 1];

		m32 sum_s = f.sv[v];
		f.sv[v] -= f.sv[v - 1];
		for (int i = v - 1; i; --i) h.lv[i] += h.lv[i + 1], f.sv[i] -= f.sv[i - 1];
		for (int j = 1; j <= v; ++j) {
			const int t0 = v / j;
			for (int t = 1; t < t0; ++t)
				add(res.lv[t], f.sv[j], h.lv[j * t] - h.lv[j * (t + 1)]);
			add(res.lv[t0], f.sv[j], h.lv[j * t0]);
		}
		for (int i = 1; i <= v; ++i)
			if (h.sv[i].x) {
				const i64 m = divide(N, i);
				const int t = sqrt(m + 0.5), t0 = v / i;

				for (int t = 1; t < t0; ++t) add(res.lv[t], h.sv[i], f.lv[t * i] - f.lv[i * (t + 1)]);
				add(res.lv[t0], h.sv[i], f.lv[t0 * i] - sum_s);
				for (int j = t0 + 1; j <= t; ++j) add(res.lv[divide_32(m, j)], h.sv[i], f.sv[j]);

				for (int j = 1; j <= t0; ++j) add(res.sv[i * j], h.sv[i], f.sv[j]);
			}

		for (int i = 1; i <= v; ++i) res.sv[i] += res.sv[i - 1];
		res.lv[v] += res.sv[v];
		for (int i = v - 1; i; --i) res.lv[i] += res.lv[i + 1];
		return res;
		};

	block l0 = calc_large([&](u64 n) { return 1; }, [&](u64 n) { return m32(n % mod); });
	block l1 = calc_large([&](u64 n) { return m32(n % mod); }, [&](u64 n) { return n %= mod, m32(n * (n + 1) / 2 % mod); });
	for (int i = 1; i <= v; ++i) l1.lv[i] = A * l0.lv[i] + B * l1.lv[i], l1.sv[i] = 0;

	auto fp = [&](u32 p) { return A + B * p; };
	auto fpp = [&](u32 p, u32 e) { return A * e + B * p; };
	return mult_powerful(attach_small(mult_large(calc_medium(fp), l1), fp), fpp);
}
signed main() {
	i64 T, n;
	m32 A, B;
        cin >> T;
	while (T--) {
		cin >> n >> A.x >> B.x;
		block f = solve(n, A, B);
		vector<m32> res(f.sv.begin() + 1, f.sv.end());
		res.insert(res.end(), f.lv.begin() + 1, f.lv.end());
		sort(res.begin(), res.end(), [](const m32 a, const m32 b) { return a.x < b.x; });
		res.erase(unique(res.begin(), res.end()), res.end());
		u32 ans = 0;
		for (auto x : res) ans ^= x.x;
		cout << ans << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 249ms
memory: 3916kb

input:

10000
988 56395756 60780067
7923 293552717 438195956
4847 24236686 75287211
6694 74889751 64994726
3720 385482711 188638093
6021 2928896 248853035
6808 310612405 330739724
4062 15289930 175596707
9583 56394035 335888448
9798 151396947 371306315
4365 216662501 351771943
1359 165179730 80942360
1436 3...

output:

6702293
422200583
304441446
69351732
421157478
210560518
504474449
12692533
331877891
385355840
275328665
310397326
67866328
533036893
27246365
72866646
467021279
34647362
411996318
297571277
334576259
221391996
496297771
222601160
232748202
470542910
115812226
192533857
361627876
443138779
2575036
...

result:

ok 10000 numbers

Test #2:

score: 0
Accepted
time: 225ms
memory: 4020kb

input:

486
685583 192056743 391870214
272484 346225796 149350515
656101 326831808 112167252
22515 203348552 60773766
1633155 194072757 22284059
57727 404929471 327406577
57598 251468713 173130016
1102497 36566124 195330260
3504399 214678339 86082351
360127 323967709 231892988
11663 225570343 56772624
39921...

output:

434223382
116245445
125541760
160318550
446061234
484145141
518392434
81977168
17947265
307371543
407160883
335339263
39598998
470162878
410893643
26179198
26198426
40422957
398293380
265153607
228078198
293572568
155169142
224586788
375283776
8481447
491498721
350950775
534322011
64802753
436909146...

result:

ok 486 numbers

Test #3:

score: 0
Accepted
time: 208ms
memory: 4040kb

input:

351
2069283 349969193 52280365
1407781 304782674 71786142
2619526 356665139 467865678
128394 19761994 158668471
4868626 435554461 55057371
228834 394703499 184531829
516241 188565552 183063603
703082 128264745 446152032
2069281 460231072 101600517
1407654 181732896 221743073
6648661 455206481 450814...

output:

319910185
369336286
50213187
67975443
429652780
316610082
64991059
22778081
332789438
497599689
331161326
417226667
247312840
325206278
489998938
119792359
144611262
188956641
12934607
448204725
376317
505473640
338284847
49730199
138622978
88198200
362403025
187282938
318525939
107779358
59656206
2...

result:

ok 351 numbers

Test #4:

score: 0
Accepted
time: 145ms
memory: 4072kb

input:

333
1016064 204524889 390112646
535822 104757052 269069192
1557487 409444563 74927504
49155 283505698 318482175
6259987 190292359 349969193
112767 52280365 304782674
191842 71786142 356665139
248003 467865678 19761994
1016062 158668471 435554461
535695 55057371 394703499
4848803 184531829 188565552
...

output:

424757689
373968255
24290918
306982012
533936667
401990420
336964323
76114089
369506627
173872187
202999923
155205263
11081034
302738228
265042946
56046100
133964275
12419321
467153573
158929408
51479146
213214379
6763076
305753342
319915377
24381258
425402644
187212393
38116675
255693248
28212987
5...

result:

ok 333 numbers

Test #5:

score: 0
Accepted
time: 5894ms
memory: 141568kb

input:

1
9994070595599 209907780 360301068

output:

39200515

result:

ok 1 number(s): "39200515"

Test #6:

score: 0
Accepted
time: 5830ms
memory: 141528kb

input:

1
9999145190306 209907780 360301068

output:

48621786

result:

ok 1 number(s): "48621786"

Test #7:

score: 0
Accepted
time: 5614ms
memory: 137928kb

input:

1
9483578929763 209907780 360301068

output:

51012486

result:

ok 1 number(s): "51012486"

Extra Test:

score: 0
Extra Test Passed