結果

問題 No.2979 直角三角形の個数
コンテスト
ユーザー Diana773
提出日時 2024-12-10 06:25:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,125 bytes
コンパイル時間 2,035 ms
コンパイル使用メモリ 169,160 KB
実行使用メモリ 17,280 KB
最終ジャッジ日時 2024-12-10 06:26:03
合計ジャッジ時間 40,700 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 20 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 计算 mu(d) 的最大范围
static const int MAXM = 1000000; // sqrt(1e12)=1e6

int mu[MAXM+1];
bool isprime[MAXM+1];

// 计算 mu(d): 使用线性筛
// mu(1)=1, 如果 d 含有平方因子则 mu(d)=0, 否则 mu(d)=(-1)^{p}, p为质因数个数
void precompute_mu() {
    vector<int> primes;
    mu[1] = 1;
    for (int i=2; i<=MAXM; i++) {
        if (!isprime[i]) {
            primes.push_back(i);
            mu[i] = -1;
        }
        for (auto &p: primes) {
            if ((ll)i*p>MAXM) break;
            isprime[i*p] = true;
            if (i%p==0) {
                mu[i*p]=0; // 有平方因子
                break;
            } else {
                mu[i*p] = -mu[i];
            }
        }
    }
}

// sumFloor(X,M): 计算 sum_{v=1}^{M} floor(X/v)
// 时间复杂度 O(sqrt(X))
ll sumFloorFunction(ll X, ll M) {
    if (X==0 || M==0) return 0;
    ll res=0;
    // 当 M > X 时，可将 M 缩小为 min(M,X), 因为 floor(X/v)=0 当 v>X
    if (M > X) M = X;
    ll v=1;
    while (v<=M) {
        ll q = X/v;
        ll nxt = X/q; 
        if (nxt > M) nxt = M;
        // v~nxt 区间 floor(X/v)=q 相同
        res += q*(nxt - v +1);
        v = nxt+1;
    }
    return res;
}

// 计算 G(M):
// G(M) = sum_{x=2}^{...} [ sum_{y=x+1}^{2x-1} floor(M/(2xy)) ]
//      = sum_{x=2}^{...} [ (sumFloor(X,2x-1)-sumFloor(X,x)) ]   其中X=floor(M/(2x))
ll Gcalc(ll M) {
    if (M < 2*3) return 0; 
    // 当 x=2 时 y=x+1=3 最小的x=2,y=3 => 2*(m+s)*(2m+s) 最小是什么?
    // 简单检查，如果 M 很小也可能直接0
    ll res=0;
    // x最大值估计：2x(x+1)<=M => x约<= sqrt(M/2)
    ll limit = (ll) floor(sqrt(M/2))+2; 
    for (ll x=2; x<=limit; x++) {
        ll X = M/(2*x);
        if (X==0) break; // 无法有有效的 y
        ll low = x+1;
        ll high = 2*x-1;
        if (low>high) continue; 
        // sum_{y=low}^{high} floor(X/y)
        // = sumFloor(X,high)-sumFloor(X,low-1)
        ll part = (sumFloorFunction(X, high)-sumFloorFunction(X, low-1));
        if (part<=0 && X<low) {
            // 如果 X<low，那么 floor(X/y)=0 对y>=low无贡献，可以break
            // 因为随x增大，这种情况只会更明显
            break;
        }
        res += part;
    }
    return res;
}

// f'(N) = sum_{odd d'≥1, d'^2 ≤ N} mu(d') * G(N/d'^2)
ll fprime(ll N) {
    ll limit = (ll)floor(sqrtl((long double)N));
    ll ans=0;
    for (int d=1; d<=limit; d+=2) { //只考虑奇数d'
        if (mu[d]==0) continue;
        ll M = N/((ll)d*d);
        if (M==0) break;
        ll val= Gcalc(M);
        if (mu[d]==1) ans+= val;
        else if (mu[d]==-1) ans-= val;
    }
    return ans;
}

// f(N)= f'(N)- f'(N/2)
ll ffunc(ll N) {
    if (N==0) return 0; 
    return fprime(N)-fprime(N/2);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 预处理 mu(d)
    precompute_mu();

    int T=1; 
    // 若需要多组输入请使用while(cin>>N)循环，这里假设只一次输入
    ll N; cin>>N;
    cout<< ffunc(N) << "\n";

    return 0;
}
0