hdu1695 (容斥原理+歐拉函數）

題意: 在1~a, 1~b中挑出(x,y)滿足gcd(x,y) = k , 求(x,y) 的對數 a,b<=10^5

思路：

轉化一下就變成了gcd(x/k,y/k)=1，x/k在[1,b/k],y/k在[1,d/k]之間的互質對數，其實這道題和hdu2841就一模一樣了，由于不能重複，限制一方小于另一方即可，假設b/k<d/k,[1,b/k]和[1,b/k]的互質對數可以用歐拉函數求出，剩餘的質因數分解用容斥就可以了，雖然我都預處理了，但是由于寫的太醜了，常數很大跑了300ms

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
bool v[maxn];
int phi[maxn],cnt=0,prime[maxn],n,m,num,sum,i;
vector<int>p[maxn];
ll ans;

void init()
{
    v[1]=v[0]=1;phi[1]=1;
    for(int i=2;i<=maxn-9;++i)
    {
        if(!v[i])phi[i]=i-1,prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=maxn-9;++j)
        {
            v[prime[j]*i]=1;
            if(i%prime[j]==0)
            {
                phi[prime[j]*i]=phi[i]*prime[j];
                break; 
            } 
            else phi[prime[j]*i]=phi[prime[j]]*phi[i];
        } 
    } 
    for(int i=2;i<=maxn-9;++i)
    {
    	int N=i;
    	for(int j=2;j*j<=N;++j)
    	{
    		if(N%j==0){
    			p[i].push_back(j);
    			while(N%j==0)
    				N/=j;
			}
		}
		if(N>1)p[i].push_back(N);
	}
}
void dfs(int pos,int lcm,int id,int x)
{
    if(id==0){
    	if((i+1)&1)
    		num+=(m/lcm);
    	else num-=(m/lcm);
    	return;
	}
   	if(pos==p[x].size())return;
   	if(lcm*p[x][pos]<=m)dfs(pos+1,lcm*p[x][pos],id-1,x);
    dfs(pos+1,lcm,id,x);
    return;
}
int getans(int x)
{
    for(i=0;i<=p[x].size();++i)
        dfs(0,1,i+1,x);
    return m-num;
}
int main()
{
    init(); 
    int t,f=0;
    scanf("%d",&t);
    while(t--)
    { 
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k==0||k>b||k>d){ printf("Case %d: 0\n",++f);continue;}
        ans=1;
        m=b/k;n=d/k;
        if(m>n)swap(n,m); 
        for(int i=2;i<=m;++i)
            ans+=1ll*phi[i];
        for(int i=m+1;i<=n;++i)
        { 
            num=sum=0;
            ans+=getans(i);
        }
        printf("Case %d: %lld\n",++f,ans);
    }
    return 0; 
}