結果
問題 |
No.2979 直角三角形の個数
|
ユーザー |
|
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 TLE * 1 |
other | AC * 24 TLE * 2 |
ソースコード
#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; }