Uva 106-Fermat vs. Pythagoras（勾股数性质） - c++编程基础

题目链接：点击打开链接

题意：给出N，x^2+y^2=z^2 小于等于N的解（互素）的个数以及小于N的个数除掉所有解（包括不互素）已经用掉的数。

度娘给出勾股数的定义：只考虑互素的解，给出勾股数公式 a=2*m*n ,b=m*m-n*n ,c=m*m+n*n; 枚举m,n ,复杂度 O(log(N)^2)

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #define maxn 1000003 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 10000007 #define pp pair
               
                 #define ull unsigned long long using namespace std; int n; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } bool vis[maxn]; void solve() { memset(vis,0,sizeof(vis)); int m=(int)sqrt(n+1),num=0,p=0; for(int i=1;i<=m;i++){ for(int j=i+1;j<=m;j++){ int c=i*i+j*j; if(c>n)break; int a=2*i*j,b=j*j-i*i; if(gcd(gcd(a,b),c)!=1)continue; vis[a]=1;vis[b]=1;vis[c]=1; num++; for(int k=2;k*c<=n;k++){ vis[a*k]=vis[b*k]=vis[c*k]=1; } } } for(int i=1;i<=n;i++) if(!vis[i])p++; printf("%d %d\n",num,p); } int main() { while (~scanf("%d", &n)) { solve(); } return 0; }