結果
問題 |
No.2979 直角三角形の個数
|
ユーザー |
|
提出日時 | 2024-12-25 06:16:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,176 bytes |
コンパイル時間 | 696 ms |
コンパイル使用メモリ | 76,840 KB |
実行使用メモリ | 7,628 KB |
最終ジャッジ日時 | 2024-12-25 06:17:06 |
合計ジャッジ時間 | 15,175 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 TLE * 1 |
other | AC * 26 |
ソースコード
#include<iostream> #include<cmath> #include<vector> #include<cassert> using namespace std; int gcd(int a,int b) { while(b) { int t=a%b; a=b; b=t; } return a; } long N; int pf[1<<20]; long quo(long a,long v){return(double)a/v;} int main() { ios::sync_with_stdio(false); cin.tie(nullptr); for(int i=2;i<1<<20;i++)if(pf[i]==0) { for(int j=i;j<1<<20;j+=i)pf[j]=i; } cin>>N; long ans=0; for(int m=2;;m++) { long up=quo(N,2*m); int l=m+1,r=(int)min(up,2*m-1L); if(l>r)break; //for(int nm=l/2*2+1;nm<=r;nm+=2)if(gcd(m,nm)==1)ans+=up/nm; vector<int>ps; { int v=m; while(v%2==0)v/=2; ps.push_back(2); while(v>1) { int p=pf[v]; ps.push_back(p); while(v%p==0)v/=p; } } long sum=0; for(int i=0;i<1<<ps.size();i++) { int t=1; for(int j=0;j<ps.size();j++)if(i>>j&1)t*=ps[j]; int nl=quo(l+t-1,t),nr=quo(r,t); long nup=quo(up,t); long cur=0; while(nl<=nr) { long q=quo(nup,nl); int nnl=(int)min((long)nr,quo(nup,q)); cur+=q*(nnl-nl+1); nl=nnl+1; } //for(int j=nl;j<=nr;j++)cur+=nup/j; if(__builtin_parity(i))sum-=cur; else sum+=cur; } ans+=sum; } cout<<ans<<endl; }