首页 > 代码库 > 不能被整除的数(南阳oj1160)(数学题)
不能被整除的数(南阳oj1160)(数学题)
不能被整除的数
时间限制:1000 ms | 内存限制:65535 KB
难度:1
- 描述
给你一个数N 再给你3个数a,b,c求1到N内即不能被a,b整除,也不能被c整除的数
- 输入
- 有多组测试数据
每次输一个数N 接下来输入3个数a,b,c
输出1~N不能被a,b,c整除的数字的个数
0<=N<=2*10^9 a,b,c 都不大于N。N=0时不做处理并且结束 - 输出
- 输出1~N不能被a,b,c整除的数字的个数
每次输出占一行 - 样例输入
1000 5 6 8 20 3 4 5
- 样例输出
600 8
- 来源
- MLFBM
- 上传者
ACM_杨明鑫
//如果暴力求解则会超时,其实这是道数学题目!
看道数学题估计都会了= =
先算在1到500中,能被2整除或能被3整除或能被7整除的数有几个:
能被2整除的:
500/2=250
或能被3整除的:
500/3=166
能被7整除的:
500/7=71
能同时被2和3整除的:
500/6=83
能同时被2和7整除的:
500/14=35
能同时被3和7整除的:
500/21=23
能同时被2、3和7整除的:
500/42=11
(图中相交区域内表示能被6整除的数,等等)在1到500中,不能被2整除,不能被3整除,不能被7整除的数有:
500-[250+166+71-83-35-23+11]=143个
#include<stdio.h> #include<string.h> int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int main() { int n,a,b,c; int k1,k2,k3,l,sum; while(scanf("%d",&n)&&n) { scanf("%d%d%d",&a,&b,&c); sum=0; k1=a*b/gcd(a,b); l=k1*c/gcd(k1,c); k2=a*c/gcd(a,c); k3=b*c/gcd(b,c); sum=n-(n/a+n/b+n/c-n/k1-n/k2-n/k3+n/l); printf("%d\n",sum); } return 0; }
不能被整除的数(南阳oj1160)(数学题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。