题意:求形成直角三角形切个边长小于L的个数,并且三边两两互素。
也就是求前L本原毕达哥拉斯三元组解的个数。令,其中m>n,。
由上式得z为直角三角形斜边且z<=L
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define maxn 1000008 bool isprime[maxn]; int prime[maxn],nprime,phi[maxn]; void getprime() { long long i,j; memset(isprime,1,sizeof(isprime)); nprime=0; for(i=2; i<maxn; i++) if(isprime[i]) { prime[nprime++]=i; for(j=i*i; j<maxn; j+=i) isprime[j]=0; } } void getphi() { for(int i=1; i<maxn; i++) phi[i]=i; for(int i=2; i<maxn; i+=2) phi[i]>>=1; for(int i=3; i<maxn; i+=2) if(phi[i]==i) for(int j=i; j<maxn; j+=i) phi[j]=phi[j]/i*(i-1); } int check[35],num; long long ans; void getcheck(int x) { num=0; int d=x; if(isprime[x]) { check[num++]=x; return; } for(int i=0; prime[i]*prime[i]<=x; i++) if(d%prime[i]==0) { check[num++]=prime[i]; while(d%prime[i]==0)d/=prime[i]; } if(d>1&&isprime[d]) check[num++]=d; } void dfs(int k,int r,int s,int n) { if(k==num) { if(r&1) ans-=n/s; else ans+=n/s; return; } dfs(k+1,r,s,n); dfs(k+1,r+1,s*check[k],n); } int main() { int t; long long l; getprime(); getphi(); scanf("%d",&t); while(t--) { scanf("%I64d",&l); ans=0; int m=sqrt(double(l-1)); for(int i=m; i>0; i--) { int p=sqrt(double(l-(long long)i*i)); if(i&1) { getcheck(i); if(p<i) dfs(0,0,1,p>>1); else dfs(0,0,1,i>>1); } else { if(i<p) ans+=phi[i]; else getcheck(i),dfs(0,0,1,p); } } printf("%I64d\n",ans); } return 0; }
时间: 2024-11-05 14:21:41