poj3090 Visible Lattice Points 欧拉函数的应用 - c++编程基础

从点（0，0）到点（x，y）画线段不经过其它点，意思就是x,y互素，由此把问题转化为求1到n内互素的数的对数，当然不要漏了(1,1)(1,0)(0,1)这三个点，接下来就是求1到n的欧拉函数值来解决这个问题，因为n的范围不是很大，所以可以直接用欧拉函数的递推方法进行求解，再打表预处理前n项即可

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // ll phi[1002]; void init() { for(int i=1;i<=1000;i++) if(i&1) phi[i]=i; else phi[i]=i/2; for(int i=3;i<=1000;i+=2) { if(phi[i] == i) { for(int j=i;j<=1000;j+=i) phi[j]=phi[j]/i*(i-1); } } for(int i=2;i<=1000;i++) phi[i] += phi[i-1]; } int main(void) { init(); int t,n; cin>>t; int cnt=0; while(t--) { cnt++; cin>>n; cout<