結果
問題 | No.2979 直角三角形の個数 |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
#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; }