結果

問題 No.2979 直角三角形の個数
ユーザー 👑 Nachia
提出日時 2024-12-03 06:36:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,711 ms / 4,000 ms
コード長 5,497 bytes
コンパイル時間 1,332 ms
コンパイル使用メモリ 104,644 KB
最終ジャッジ日時 2025-02-26 10:44:58
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;
#include <atcoder/modint>
using Modint = atcoder::static_modint<998244353>;
#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
void testcase(){
    i64 N; cin >> N;
    N /= 2;
    if(N < 6){
        cout << "0\n"; return;
    }
    i64 R = 0;
    for(i64 d=1ll<<20; d>=1; d>>=1) if((R+d)*(R+d) <= N) R += d;
    i64 L = R;
    
    i64 sqfree_border = min<i64>(R, 30000);
    vector<i64> Sqfree(sqfree_border + 1);
    for(i64 i=1; i<=sqfree_border; i++) Sqfree[i] = nachia::CountSquarefree(N/i);
    vector<i64> sqfree(N / sqfree_border + 1, 0);
    for(i64 i=1; i*sqfree_border<=N; i+=2) sqfree[i] += 1;
    for(i64 p=2; p*p<=N/sqfree_border; p++) if(sqfree[p*p]){
        for(i64 q=1; p*p*q<=N/sqfree_border; q++) sqfree[p*p*q] = 0;
    }
    for(i64 i=1; i<i64(sqfree.size()); i++) sqfree[i] += sqfree[i-1];
    auto sqfree_access = [&](i64 n){
        if(n <= sqfree_border) return Sqfree[n];
        return sqfree[N/n];
    };
    
    for(i64 i=sqfree_border; i>=1; i--) Sqfree[i] -= sqfree_access(i*2);
    
    if(N <= 5000000){
        vector<i64> A(N+1);
        for(i64 n=1; n*n<=N; n++){
            for(i64 m=1; m<n && n*(n+m)<=N; m++){
                A[n*(n+m)] += 1;
            }
        }
        i64 ans = 0;
        for(i64 i=1; i<=N; i++) ans += sqfree_access(i) * A[i];
        cout << ans << endl;
    }
    else{
        i64 Q = min<i64>(R, 10000);
        i64 P = N / Q;
        i64 ans = 0;
        for(i64 n=1; n*n<=P; n++){
            for(i64 m=1; m<n && n*(n+m)<=P; m++){
                ans += sqfree_access(n*(n+m));
            }
        }
        vector<i64> Q2(Q+1);
        for(i64 q=1; q<=Q; q++){
            i64 p = N / q;
            while(R*R > p) R--;
            while(L*L*2 > p) L--;
            i64 f = L * (L - 1) / 2;
            for(i64 i=L+1; i<=R; i++) f += p / i - i;
            Q2[q] = f;
        }
        for(i64 q=1; q<Q; q++) ans += sqfree_access(N/q) * (Q2[q] - Q2[q+1]);
        cout << ans << endl;
    }
    
}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0