結果

問題 No.2979 直角三角形の個数
ユーザー 👑 testestest
提出日時 2024-11-21 21:47:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,448 ms / 4,000 ms
コード長 917 bytes
コンパイル時間 3,280 ms
コンパイル使用メモリ 249,748 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-12-02 23:30:09
合計ジャッジ時間 8,418 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
int main(){
    i64 N;
    cin >> N;
    i64 sqrtN=sqrt(N)+3;
    vector<bool>prime(sqrtN,true);
    vector<int>mu(sqrtN,1);
    for(i64 i=2;i<sqrtN;i++)if(prime[i]){
        mu[i]*=-1;
        for(i64 j=2*i;j<sqrtN;j+=i)prime[j]=false,mu[j]*=-1;
        for(i64 j=i*i;j<sqrtN;j+=i*i)mu[j]=0;
    }
    auto f=[&](i64 n){
        //return Σ_{x,y} n/(2(x+y)(2x+y))
        if(n<12)return 0LL;
        i64 ans=0;
        i64 V=cbrt(n);
        i64 B=n/V;
        i64 X=(sqrt(4*B+1)-3)/4;
        for(i64 x=1;x<=X;x++){
            i64 Y=(sqrt(x*x+2*B)-3*x)/2;
            for(i64 y=1;y<=Y;y++)ans+=n/(2*(x+y)*(2*x+y));
        }
        vector<i64>cnt(V+1);
        for(i64 i=1;i<=V;i++){
            i64 U=n/i;
            i64 X=(sqrt(4*U+1)-3)/4;
            for(i64 x=1;x<=X;x++)cnt[i]+=(i64)((sqrt(x*x+2*U)-3*x)/2);
        }
        for(i64 i=1;i<V;i++)ans+=i*(cnt[i]-cnt[i+1]);
        return ans;
    };
    i64 ans=0;
    for(i64 i=1;12*i*i<=N;i+=2)if(mu[i])ans+=mu[i]*(f(N/i/i)-f(N/2/i/i));
    cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0