結果
問題 |
No.2979 直角三角形の個数
|
ユーザー |
|
提出日時 | 2024-12-03 16:43:06 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,488 bytes |
コンパイル時間 | 805 ms |
コンパイル使用メモリ | 88,276 KB |
実行使用メモリ | 31,616 KB |
最終ジャッジ日時 | 2024-12-03 16:43:52 |
合計ジャッジ時間 | 46,019 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 TLE * 1 |
other | AC * 15 WA * 4 TLE * 7 |
ソースコード
#include <iostream> #include <string.h> #include <stdio.h> #include <math.h> using namespace std; typedef long long LL; const int N=10000005; const int M=1005; bool prime[N]; int p[N]; int pri[M]; int num[M]; int k,cnt,tmp,tmp1,count; void isprime() { k=0; int i,j; memset(prime,true,sizeof(prime)); for(i=2;i<N;i++) { if(prime[i]) { p[k++]=i; for(j=i+i;j<N;j+=i) { prime[j]=false; } } } } void Find(int n) { cnt=0; int t=(int)sqrt(n*1.0),i,a; for(i=0;p[i]<=t;i++) { if(n%p[i]==0) { a=0; pri[cnt]=p[i]; while(n%p[i]==0) { a++; n/=p[i]; } num[cnt]=2*a; cnt++; } } if(n>1) { pri[cnt]=n; num[cnt]=2; cnt++; } } void dfs(int dept, LL product=1) { if(dept==cnt) { if(product%2==0&&product>tmp&&product<tmp1) count++; return; } for(int i=0;i<=num[dept];i++) { dfs(dept+1,product); product*=pri[dept]; } } int main() { int n; scanf("%d",&n); isprime(); int ans = 0; for (int i = 1; i <= n; ++i) { count=0; tmp=(LL)(sqrt(2.0)*i); tmp1=2*i; Find(i); dfs(0,1); ans += count; } cout << ans << '\n'; return 0; }