时间限制: 1 Sec 内存限制: 128 MB
题目描述
There are two lights that blink at regular intervals. When each one blinks, it turns on and then immediately back off; they don’t toggle. They are both off at time t=0. The first one blinks at t=p,2p,3p,… seconds; the second one blinks at t=q,2q,3q,… seconds. Once they start, they both keep blinking forever. It is very exciting to see them blink at the same time (on the same second). But your patience is going to run out eventually, in s seconds. Will they blink at same time between t=1 and t=s (inclusive)? Write a program that can answer this question, quick, before they start blinking again!
Figure 1: Illustration of the sample inputs. A black circle means the light is off, a white circle means the light blinks at that second. The arrows above point out times when both lights blink.
输入
Input consists of one line containing three space-separated integers p, q, and s. The bounds are 1≤p,q≤100 and 1≤s≤10000. The first light blinks every p seconds, the second every q seconds. The value of s represents the maximum number of seconds to consider when determining if the two lights blink at the same time.
输出
Output yes if the two lights blink on the same second between time 1 and time s, or no otherwise.
样例输入
2 5 20
样例输出
yes
暴力模拟大水题
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10010;
typedef pair<int,int>P;
bool vis1[N],vis2[N];
int main()
{
int p,q,s;
scanf("%d%d%d",&p,&q,&s);
for(int i=p;i<N;i+=p) vis1[i]=true;
for(int i=q;i<N;i+=q) vis2[i]=true;
bool flag=false;
for(int i=1;i<=s;i++)
{
if(vis1[i] && vis2[i])
{
flag=true;
break;
}
}
if(flag) puts("yes");
else puts("no");
return 0;
}
Moriarty Yang 