本文主要是介绍qwb与支教(二分+容斥原理),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
qwb与支教
Description
qwb同时也是是之江学院的志愿者,暑期要前往周边地区支教,为了提高小学生的数学水平。她把小学生排成一排,从左至右从1开始依次往上报数。
玩完一轮后,他发现这个游戏太简单了。于是他选了3个不同的数x,y,z;从1依次往上开始报数,遇到x的倍数、y的倍数或z的倍数就跳过。如果x=2,y=3,z=5;第一名小学生报1,第2名得跳过2、3、4、5、6,报7;第3名得跳过8、9、10,报11。
那么问题来了,请你来计算,第N名学生报的数字是多少?
Input
多组测试数据,处理到文件结束。(测试数据数量<=8000)
每个测试例一行,每行有四个整数x,y,z,N。( 2≤x,y,z≤107,1≤N≤1017)。
Output
Output
对于每个测试例,输出第N名学生所报的数字,每个报数占一行。
Sample Input
- 1
- 2
Sample Output
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);
}
ll lcm(ll x,ll y){return x/gcd(x,y)*y;
}
ll n,x,y,z;
int judge(ll mid){ll a;a=mid-(mid/x+mid/y+mid/z-mid/lcm(x,y)-mid/lcm(x,z)-mid/lcm(y,z)+mid/lcm(x,lcm(y,z)));//找出在<=mid的数中有多少非XYZ的倍数的数 if(a>=n)return 1;return 0;
}
int main()
{while(scanf("%lld%lld%lld%lld",&x,&y,&z,&n)!=EOF){ll low,high,mid,t;low=1;high=1e18;while(low<=high){mid=(high+low)/2;if(judge(mid)){high=mid-1;t=mid;}else{low=mid+1;}}printf("%lld\n",t);}return 0;}
这篇关于qwb与支教(二分+容斥原理)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!