結果

問題 No.1653 Squarefree
ユーザー 👑 NachiaNachia
提出日時 2024-01-28 17:54:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,849 ms / 2,000 ms
コード長 3,252 bytes
コンパイル時間 769 ms
コンパイル使用メモリ 69,600 KB
実行使用メモリ 82,092 KB
最終ジャッジ日時 2024-01-28 17:55:08
合計ジャッジ時間 39,558 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,742 ms
81,456 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 1 ms
6,676 KB
testcase_03 AC 16 ms
6,676 KB
testcase_04 AC 1 ms
6,676 KB
testcase_05 AC 1 ms
6,676 KB
testcase_06 AC 2 ms
6,676 KB
testcase_07 AC 1 ms
6,676 KB
testcase_08 AC 1 ms
6,676 KB
testcase_09 AC 2 ms
6,676 KB
testcase_10 AC 2 ms
6,676 KB
testcase_11 AC 2 ms
6,676 KB
testcase_12 AC 1 ms
6,676 KB
testcase_13 AC 1,709 ms
82,088 KB
testcase_14 AC 1,731 ms
81,964 KB
testcase_15 AC 1,695 ms
82,092 KB
testcase_16 AC 1,719 ms
81,888 KB
testcase_17 AC 1,702 ms
81,992 KB
testcase_18 AC 1,690 ms
81,836 KB
testcase_19 AC 1,712 ms
81,820 KB
testcase_20 AC 1,708 ms
82,092 KB
testcase_21 AC 1,703 ms
82,092 KB
testcase_22 AC 1,724 ms
82,092 KB
testcase_23 AC 1,669 ms
82,072 KB
testcase_24 AC 1,694 ms
81,244 KB
testcase_25 AC 1,710 ms
81,892 KB
testcase_26 AC 1,849 ms
82,092 KB
testcase_27 AC 1,691 ms
81,868 KB
testcase_28 AC 1,575 ms
76,720 KB
testcase_29 AC 1,699 ms
81,948 KB
testcase_30 AC 1,667 ms
82,092 KB
testcase_31 AC 1,699 ms
82,092 KB
testcase_32 AC 1,693 ms
82,092 KB
testcase_33 AC 1,697 ms
82,092 KB
testcase_34 AC 1,705 ms
82,092 KB
testcase_35 AC 1,717 ms
82,092 KB
testcase_36 AC 1,694 ms
81,948 KB
testcase_37 AC 1,678 ms
81,820 KB
testcase_38 AC 1,730 ms
81,784 KB
testcase_39 AC 1,692 ms
81,816 KB
testcase_40 AC 1,747 ms
81,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <cmath>

#include <cassert>

namespace nachia{

namespace internal{

// mod 2^64
constexpr 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 <= x
        static 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 nachia

namespace 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);
    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;
}
0