HDU 2841 Visible Trees - c++编程基础

题意：就是给定一个坐标(n,m)，求(1,1)到(n,m)区间内x与y互质的坐标数。

思路：利用容斥从2到n，遍历与m互质的个数。

 
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
using namespace std;  
  
typedef __int64 LL;  
const int N=1000005;  
const LL II=1000000007;  
const int INF=0x3f3f3f3f;  
const double PI=acos(-1.0);  
  
LL n,m,pri[N];  
  
LL prime(LL x)  
{  
    LL i,j,numi=0;  
    for(i=2;i*i<=x;i++)  
        if(x%i==0)  
        {  
            pri[numi++]=i;  
            while(x%i==0)  
                x/=i;  
        }  
    if(x>1)  
        pri[numi++]=x;  
    return numi;  
}  
  
LL dfs(LL k,LL n)  
{  
    LL i,j,t,numi;  
    numi=prime(k);  
    LL sum=0;  
    for(i=1;i<(1<





#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef __int64 LL;
const int N=1000005;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

LL n,m,pri[N];

LL prime(LL x)
{
    LL i,j,numi=0;
    for(i=2;i*i<=x;i++)
        if(x%i==0)
        {
            pri[numi++]=i;
            while(x%i==0)
                x/=i;
        }
    if(x>1)
        pri[numi++]=x;
    return numi;
}

LL dfs(LL k,LL n)
{
    LL i,j,t,numi;
    numi=prime(k);
    LL sum=0;
    for(i=1;i<(1<

AC代码：