Hide and Seek

NC252839. Hide and Seek

描述

Eva is playing a special "hide and seek" game with Colin. Dislike the traditional one, Eva picks a hidden positive integer $x$ and let Colin guess.

First Eva will tell Colin a positive integer $a$ and she guarantees that $x\le a$ .

Then Eva will show Colin $m$ constraints: each constraint is given by two non-negative integer $b_j,c_j$ , meaning that $b_j \text{ } \text{mod} \text{ } x = c_j \text{ } (1 \le j \le m)$ .

Colin wants to enumerate all possible integers, but he don't know there are how many of them. Can you tell Colin how many positive integers can suit all constraints above?

It's guaranteed there exists at least one integer which can suit all constraints above.

输入描述

The first line contains two integers  , representing the number of constraints and the upper bound of hidden integer .

For the following  lines, each line contains two integers  , represents  .

输出描述

A single line contains an integer, representing the number of positive integers which can suit all given constraints.

示例1

输入:

2 10
7 1
8 2

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 66ms, 内存消耗: 3996K, 提交时间: 2023-07-30 16:19:45

#include<bits/stdc++.h>
using namespace std;
int m,a,b,c,g,l=1,i=1,ans;
int main(){
	cin>>m>>a;
	while(m--){
		scanf("%d%d",&b,&c);
		g=__gcd(b-c,g);
		l=max(l,c+1);
	}
	if(!g){
		cout<<a-l+1;
		return 0;
	}
	for(;i*i<g;i++)
		if(g%i==0&&g/i<=a&&g/i>=l) ans++;
	cout<<ans;
}

C++(g++ 7.5.0) 解法, 执行用时: 57ms, 内存消耗: 432K, 提交时间: 2023-07-09 21:03:20

#include<bits/stdc++.h>
using namespace std;
int m,a,b,c,gc,l=1,i=1;
int main(){
	cin>>m>>a;
	while(m--){
		scanf("%d%d",&b,&c);
		gc=__gcd(b-c,gc);
		l=max(l,c+1);
	}
	for(;i*i<gc;i++)
		if(gc%i==0&&gc/i<=a&&gc/i>=l) m++;
	cout<<(gc?++m:a-l+1);
	return 0;
}

上一题

下一题

详情