結果

問題 No.2979 直角三角形の個数
ユーザー Diana773Diana773
提出日時 2024-12-10 07:51:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,909 bytes
コンパイル時間 1,647 ms
コンパイル使用メモリ 168,960 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-12-10 07:51:50
合計ジャッジ時間 20,210 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
8,704 KB
testcase_01 AC 2 ms
10,624 KB
testcase_02 AC 2 ms
8,704 KB
testcase_03 AC 2 ms
10,272 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 3 ms
5,248 KB
testcase_13 AC 3 ms
5,248 KB
testcase_14 AC 9 ms
5,248 KB
testcase_15 AC 9 ms
5,248 KB
testcase_16 AC 25 ms
5,248 KB
testcase_17 AC 59 ms
5,248 KB
testcase_18 AC 168 ms
5,248 KB
testcase_19 AC 231 ms
5,248 KB
testcase_20 AC 653 ms
5,248 KB
testcase_21 AC 1,018 ms
5,248 KB
testcase_22 TLE -
testcase_23 TLE -
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 5 ms
5,248 KB
testcase_28 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using i64 = long long;

// 根据您给出的代码片段构造G函数
// G(N) = Σ_{x,y} floor(N/(2(x+y)(2x+y))) ，x,y≥1且当2(x+y)(2x+y)>N时为0
// 按照您给的代码逻辑:

// G 函数实现（来自您给的 Lambda G 思路，稍作函数化）
i64 G_func(i64 n){
    if(n<12)return 0LL;
    i64 ans=0;
    // V=cbrt(n), B=n/V
    long double nd=(long double)n;
    long double vv=cbrt(nd);
    i64 V=(i64)floor(vv);
    // 保守微调，确保 (V+1)^3<=N时可增1
    while(((long double)(V+1)*(V+1)*(V+1))<=nd) V++;
    while((long double)V*V*V>nd) V--;

    i64 B=n/V;
    // X = (sqrt(4B+1)-3)/4
    long double tmp=4.0L*B+1.0L;
    long double sq=sqrtl(tmp);
    long double Xd=(sq-3.0L)/4.0L;
    i64 X=(i64)floor(Xd);

    i64 cn=0;
    for(i64 x=1;x<=X;x++){
        long double temp=(long double)(x*x+2*B);
        long double YY=sqrtl(temp);
        long double Yd=(YY-3*x)/2.0L;
        i64 Y=(i64)floor(Yd);
        if(Y<1) continue;
        for(i64 y=1;y<=Y;y++){
            i64 val=2*(x+y)*(2*x+y);
            ans+=n/val;
            cn++;
        }
    }

    vector<i64> cnt(V+1,0);
    for(i64 i=1;i<=V;i++){
        i64 U=n/i;
        long double tmp2=(long double)(4*U+1);
        long double sq2=sqrtl(tmp2);
        long double X2d=(sq2-3)/4.0L;
        i64 X2=(i64)floor(X2d);
        for(i64 x=1;x<=X2;x++){
            long double tt=(long double)(x*x+2*U);
            long double yyy=sqrtl(tt);
            long double Y2d=(yyy-3*x)/2.0L;
            i64 Y2=(i64)floor(Y2d);
            if(Y2>=1) cnt[i]+=Y2;
        }
    }

    for(i64 i=1;i<V;i++){
        ans+=i*(cnt[i]-cnt[i+1]);
    }

    return ans;
}

// 计算μ(d) Möbius函数的函数
// d为正整数
int mu_of_d(i64 d) {
    if(d==1) return 1;
    // 分解d判断是否有平方因子，并计数质因数个数
    int factors=0;
    i64 x=d;
    for(i64 p=2; p*p<=x; p++){
        if(x%p==0){
            factors++;
            x/=p;
            if(x%p==0) return 0; // 有平方因子
        }
    }
    if(x>1) factors++;
    return (factors%2==0)?1:-1;
}

// f'(X)= sum_{odd d'≥1} mu(d') * G(X/(d'^2))，d'^2 ≤ X
// 为减少计算时间，对于非常大X可能较慢，不过题中示例10000可接受。
i64 f_prime(i64 X) {
    if(X<1) return 0;
    i64 limit=(i64)floor(sqrtl((long double)X));
    i64 ans=0;
    // 枚举odd d'
    for(i64 d=1; d<=limit; d+=2){
        int mu_val = mu_of_d(d);
        if(mu_val==0) continue;
        i64 div = X/(d*d);
        if(div<1) break;
        i64 g_val=G_func(div);
        ans += mu_val*g_val;
    }
    return ans;
}

// f(N)=f'(N)-f'(N/2)
i64 f_func(i64 N){
    i64 fpN=f_prime(N);
    i64 fpN2=f_prime(N/2);
    return fpN - fpN2;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 N;cin>>N;
    i64 result = f_func(N);
    cout<<result<<"\n";
    return 0;
}
0