QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#682704 | #8327. 积性函数求和 $10^{13}$ 方便 FFT 版 | zydy | AC ✓ | 5894ms | 141568kb | C++17 | 9.6kb | 2024-10-27 17:02:03 | 2024-10-27 17:02:03 |
Judging History
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