hdu2841(容斥原理+分解质因数)Visible Trees

小鱼儿 2024-02-17 23:46 5阅读 0赞

/*
    题目大意:在一个n*m的方格中一个人站在（0,0），每个方格都有树，求他能看到多少颗树
    设某点的坐标为（x,y)，则求的是x/y的不同数目,那么问题就转换成了求两个区间内的互质的对数
    如果可以约分，那么他们约分后的互质在前面已经计算过了 
    */ 
    //求区间[a,b]与[a,b]互质数多少对 
    #include<cstdio>
    #include<iostream>
    #include<vector>
    #define ll long long
    using namespace std;
    const int mx=100005;
    int n,a,b;
    vector<int> x[mx];
    int vis[mx];
    void prime()
    {
    	//预处理1~mx内的数的素因子 
    	for(int i=2;i<mx;++i)
    	if(!vis[i])
    	{
    		for(int j=i;j<mx;j+=i)
    		{
    			vis[j]=1;
    			x[j].push_back(i);
    		}
    	}
    }
    int solve(int a,int p)
    {
    	//求区间[1,a]与p互质的数的个数
    	int ans=a;
    	for(int i=1;i<(1<<x[p].size());++i)
    	{
    		int cnt=0,k=1;
    		for(int j=0;j<x[p].size();++j)
    		if(i&(1<<j)) k*=x[p][j],++cnt;
    		if(cnt&1) ans-=a/k;
    		else ans+=a/k;
    	}
    	return ans;
    }
    int main(){
    	prime();
    	scanf("%d",&n);
    	while(n--)
    	{
    		scanf("%d%d",&a,&b);
    		ll ans=a;//1不满足容斥原理 
    		for(int i=2;i<=b;++i)
    		{
    			ans+=solve(a,i);
    		}
    		printf("%lld\n",ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu2841(容斥原理+分解质因数)Visible Trees

/ 题目大意:在一个nm的方格中一个人站在（0,0），每个方格都有树，求他能看到多少颗树设某点的坐标为（x,y)，则求的是x/y的不同数目,那么问题就

小鱼儿/ 2024年02月17日 23:46/ 0 赞/ 6 阅读

相关 hdu4407（容斥原理+分解质因数）Sum

题目大意是第一行输入T，第二行输入n，m，一个数组a\[i\]=i,下面m行每行一个操作，输入1,x,p，则表示把a\[i\]修改为p,输入2,x,y,p，则表示询问\[x,y

矫情吗；*/ 2024年02月17日 23:45/ 0 赞/ 48 阅读

相关 hdu4135（容斥原理）Co-prime

题目大意是：输入A,B,N，求\[A,B\]区间内与N互质的数的个数 include<cstdio> include<iostream> inclu

灰太狼/ 2024年02月17日 23:44/ 0 赞/ 72 阅读

相关 hdu1695（容斥原理）

求（1，b）区间和（1，d）区间里面gcd(x, y) = k的数的对数（1<=x<=b , 1<= y <= d）。 b和d分别除以k之后的区间里面，只需要求gcd(x,

一时失言乱红尘/ 2024年02月17日 23:41/ 0 赞/ 57 阅读

相关 Hdu 1695 GCD (数论容斥原理)

参考了：[HDU 1695 GCD 【数论，容斥原理】 - 脑残 - 博客频道 - CSDN.NET][HDU 1695 GCD _ - _ - _ - CSDN.NET]

落日映苍穹つ/ 2022年08月26日 08:10/ 0 赞/ 159 阅读

相关 HDU 2841 Visible Trees （容斥原理+素因子分解）

HDU 2841 Visible Trees （容斥原理+素因子分解）：[http://acm.hdu.edu.cn/showproblem.php?pid=2841][htt

﹏ヽ暗。殇╰゛Y/ 2022年07月26日 00:08/ 0 赞/ 149 阅读

相关 hdu 1695 GCD (欧拉函数+容斥原理+素因子分解)

hdu 1695 GCD (欧拉函数+容斥原理+素因子分解) ：[http://acm.hdu.edu.cn/showproblem.php?pid=1695][http_ac

绝地灬酷狼/ 2022年07月25日 15:58/ 0 赞/ 175 阅读

相关 HDU 1695 GCD （容斥原理）

[HDU 1695][] 题意：求有多少对(x,y), (1<=x<=b,1<=y<=d), 满足gcd(x,y)=k。题解：注意到gcd(x,y)=k,说明x,y

男娘i/ 2022年07月12日 09:55/ 0 赞/ 240 阅读

相关 HDU-4135 Co-prime(容斥原理)

Co-prime Given a number N, you are asked to cou

野性酷女/ 2022年06月10日 13:55/ 0 赞/ 211 阅读

相关 HDU-2841 Visible Trees (莫比乌斯反演)

Visible Trees There are many trees forming

谁践踏了优雅/ 2022年06月10日 13:53/ 0 赞/ 213 阅读