結果
問題 | No.1653 Squarefree |
ユーザー |
👑 ![]() |
提出日時 | 2024-01-28 17:50:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,239 bytes |
コンパイル時間 | 647 ms |
コンパイル使用メモリ | 55,164 KB |
最終ジャッジ日時 | 2025-02-19 00:34:01 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 TLE * 29 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:112:26: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 112 | long long L, R; scanf("%lld%lld", &L, &R); | ~~~~~^~~~~~~~~~~~~~~~~~~~
ソースコード
#include <vector>#include <cassert>namespace nachia{namespace internal{// mod 2^64constexpr unsigned long long PowerOfULongLong(unsigned long long a, unsigned long long i){unsigned long long res = 1;while(i){ if(i&1){ res *= a; } i /= 2; a *= a; }return res;}}unsigned long long FloorOfKthRoot(unsigned long long real, unsigned long long k){using u64 = unsigned long long;assert(k != 0);if(real <= 1) return real;if(k >= 64) return 1;if(k == 1) return real;struct Precalc{// a^i <= xstatic constexpr bool lesseq(u64 a, int i, u64 x) {if (a == 0) return true;for(int j=0; j<i; j++) x /= a;return x >= 1;}unsigned long long BORDER[64];constexpr Precalc() : BORDER() {for (int idx = 2; idx <= 63; idx++) {u64 l = 0, r = 1ull << 33;while (l + 1 < r) {u64 m = (l + r) / 2;if (lesseq(m, idx, ~0ull)) l = m;else r = m;}BORDER[idx] = r;}};};constexpr Precalc precalc;u64 l = 0, r = precalc.BORDER[k];if(real < r) r = real;while (l + 1 < r) {u64 m = (l + r) / 2;if(internal::PowerOfULongLong(m, k) <= real) l = m;else r = m;}return l;}unsigned long long CeilOfKthRoot(unsigned long long real, unsigned long long k){if(real <= 1) return real;if(k >= 64) return 2;if(k == 1) return real;unsigned long long x = FloorOfKthRoot(real, k);if(internal::PowerOfULongLong(x, k) != real) x++;return x;}} // namespace nachianamespace nachia{long long CountSquarefree(long long n){using i64 = long long;i64 s = 0;auto getMobius = [&](i64 n){std::vector<bool> sieve(n+1, true);std::vector<signed char> mu(n+1, 1);for(i64 i=2; i<=n; i++) if(sieve[i]){mu[i] = -1;for(i64 j=i*i; j<=n; j+=i) sieve[j] = false;for(i64 j=i*2; j<=n; j+=i) mu[j] = -mu[j];for(i64 j=i*i; j<=n; j+=i*i) mu[j] = 0;}return mu;};if(n <= 4000){auto mu = getMobius(n+1);for(i64 i=1; i*i<=n; i++) s += n/(i*i) * mu[i];return s;}i64 I = nachia::FloorOfKthRoot(n, 5) * 2;i64 D = nachia::FloorOfKthRoot(n/(I+1), 2);auto mu = getMobius(D+1);std::vector<int> Mf(D+1);for(i64 i=1; i<=D; i++) Mf[i] = Mf[i-1] + mu[i];std::vector<i64> Md(I+1);for(i64 i=I; i>=1; i--){i64 m = 1;i64 x = nachia::FloorOfKthRoot(n/i, 2);i64 Dx = nachia::FloorOfKthRoot(x, 2);i64 Rx = x / (Dx+1);i64 r = 2;for( ; i*r*r<=I; r++) m -= Md[i*r*r];for( ; r<=Rx; r++) m -= Mf[x/r];for(i64 d=1; d<=Dx; d++) m -= mu[d] * (x/d - Rx);Md[i] = m; s += m;}for(i64 i=1; i<=D; i++) s += mu[i] * (n/(i*i) - I);return s;}} // namespace nachia#include <cstdio>int main(){long long L, R; scanf("%lld%lld", &L, &R);long long ans = nachia::CountSquarefree(R) - nachia::CountSquarefree(L-1);printf("%lld\n", ans);return 0;}