NYOJ--How many integers can you find

分手后的思念是犯贱 2022-08-26 12:28 2阅读 0赞

## How many integers can you find ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 1

描述

给你三个数,n,m1,m2,找出所有小于n的能被m1或m2整除的数的个数。

输入

输入包含多组测试数据，每组数据占一行。  
0<n<2^31,0<m1，m2<=10。

输出

每组数据输出占一行。

样例输入

12 2 3

样例输出

7

来源

[爱生活][Link 1]

解析：如果这道题你想用暴力的话就肯定TLE了，这道题用到离散数学中的简单的容斥原理，其实就是集合之间的交并关系，比如A并B=A+B-A交B，算是用到这个公式吧，如果还想更多了解的可以继续百度，知道了这个，就是求m1和m2的最小公倍数，不要想当然的认为m1×m2就是最小公倍数，这个可以利用欧几里德算法来求，剩下就很水了，另外HDU上面也有类似这道题，但是比这个要麻烦，算是这个加强版的，有兴趣的话可以去搜一下哈！

#include <iostream>
    using std::endl;
    using std::cout;
    using std::cin;
    //欧几里得求最大公约数  
    int gcd(int a, int b)   
    {  
    	if (a % b == 0) {  
    		return b;  
    	} else {  
    		return gcd(b, a % b);  
    	}  
    }  
    int main()
    {
    	int n,m1, m2;
    	while (cin >> n >> m1 >> m2)
    	{
    		if (m1 != m2)
    			cout << (n-1)/m1+(n-1)/m2-(n-1)/((m1*m2)/gcd(m1,m2))<< endl;
    		else
    			cout << (n-1)/m1 << endl;
    	}
    	return 0;
    }

[Link 1]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=%E7%88%B1%E7%94%9F%E6%B4%BB

发表评论取消回复

表情：

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

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

相关阅读

相关 hdu1796（容斥原理模板，三种方法实现）How many integers can you find

dfs是实现时间复杂度是2^n，二进制时间复杂度是n\2^n 题目大意：给定n和一个大小为m的集合，集合元素为非负整数。为1...n-1中能被集合里任意一个数整除的数字个数。

Dear 丶/ 2024年02月17日 23:39/ 0 赞/ 39 阅读

相关 NYOJ--How many integers can you find

How many integers can you find 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 1 描述给你三个数,n,m

分手后的思念是犯贱/ 2022年08月26日 12:28/ 0 赞/ 3 阅读

相关 Hdu 1796 How many integers can you find (容斥原理递归及循环的一般写法)

题意：给出n和由m个元素的集合，求小于n且是集合中任意元素的倍数的数有多少个。把集合中的0先去掉。 include <cstdio> int d

朱雀/ 2022年08月26日 04:55/ 0 赞/ 129 阅读

相关 HDU 2141 can you find it?

Can you find it? Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/10000

小鱼儿/ 2022年07月16日 17:37/ 0 赞/ 131 阅读

相关 HDU 2266 How Many Equations Can You Find （技巧性dfs）

How Many Equations Can You Find Problem Description Now give you an string whic

「爱情、让人受尽委屈。」/ 2022年06月13日 07:50/ 0 赞/ 142 阅读

相关 HDU-1796 How many integers can you find(容斥原理)

[How many integers can you find][] Now you get a number N, and a M

水深无声/ 2022年06月10日 13:25/ 0 赞/ 165 阅读

相关 HDU2141-Can you find it?

Can you find it? Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/10000

左手的ㄟ右手/ 2022年06月09日 08:48/ 0 赞/ 166 阅读

相关 How many integers can you find————（算术基本定理+容斥）

Now you get a number N, and a M-integers set, you should find out how many integers whic

水深无声/ 2022年05月18日 00:11/ 0 赞/ 162 阅读

相关 HDU 2011 How Many Equations Can You Find ——————DFS

How Many Equations Can You Find Time Limit: 2000/1000 MS (Java/Others) Memory Limit:

旧城等待，/ 2022年05月14日 11:22/ 0 赞/ 141 阅读

相关 soj 3137 Simple Computing 容斥原理 hdu 1796 How many integers can you find

/ hdu1796.c Created on: 2011-10-3 Author: bjfuwangzhu

╰+哭是因爲堅強的太久メ/ 2021年12月20日 16:25/ 0 赞/ 198 阅读