先分享两道这两周学的关于数学的题（）

P1865 A % B Problem

题目背景

题目名称是吸引你点进来的。
实际上该题还是很水的。

题目描述

给定 $l,r$，求区间 $[l,r]$ 内质数的个数。

输入格式

第一行有两个整数，分别代表询问次数 $n$ 和 给定区间的右端点最大值 $m$。

接下来 $n$ 行，每行两个整数 $l,r$，代表一次查询。

输出格式

对于每次查询输出一行，若 $l,r\in [1,m]$，则输出区间质数个数，否则输出 Crossing the line。

输入输出样例 #1

输入 #1

2 5
1 3
2 6

输出 #1

2
Crossing the line

说明/提示

数据范围与约定

1. 对于 $20\%$ 的数据，保证 $n,m\le 10$。
2. 对于 $100\%$ 的数据，保证 $1\le n\le 1000$，$1\le m\le 10^6$，$-10^9\le l\le r\le 10^9$。

思路

1. 根据输入的m找到m以内的所有质数，并把他们储存起来；
2. 使用另一个数组把质数对应的下标++；再用前缀和就可以得到某个数之前一共有多少个质数；
3. 最后记得判断一下l,r的范围即可；

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long 

const int N=1e6+8;
vector<int> q;
int vis[N],s[N];

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=2;i<=m;i++){
		if(vis[i]==0)	q.push_back(i);
		for(int j=0;i*q[j]<=m;j++){
			vis[i*q[j]]=1;
			if(i%q[j]==0)	break;
		}
	}
	for(int i=0;i<q.size();i++){
		s[q[i]]++;
	}
	for(int i=1;i<=m;i++){
		s[i]=s[i-1]+s[i];
	}
	while(n--){
		int l,r;
		cin>>l>>r;
		if(l<1 || r<1 || l>m || r>m){
			cout<<"Crossing the line"<<"\n";
		}
		else{
			int ans=s[r]-s[l-1];
			cout<<ans<<"\n";
		}
	}
	return 0;
}

P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

题目描述

输入两个正整数 $x_0,y_0$，求出满足下列条件的 $P,Q$ 的个数：

1. $P,Q$ 是正整数。

2. 要求 $P,Q$ 以 $x_0$ 为最大公约数，以 $y_0$ 为最小公倍数。

试求：满足条件的所有可能的 $P,Q$ 的个数。

输入格式

一行两个正整数 $x_0,y_0$。

输出格式

一行一个数，表示求出满足条件的 $P,Q$ 的个数。

输入输出样例 #1

输入 #1

3 60

输出 #1

4

说明/提示

$P,Q$ 有 $4$ 种：

1. $3,60$。
2. $15,12$。
3. $12,15$。
4. $60,3$。

对于 $100\%$ 的数据，$2\le x_0,y_0\le {10}^5$。

【题目来源】

NOIP 2001 普及组第二题

思路

1. 由题目中第二个条件可得，x0 * y0=p * q；
2. 从最大公因数开始遍历到最小公倍数，统计满足条件的数量；

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

int a,b,ans;

signed main()
{
	cin>>a>>b;
	int m=a*b;
	for(int i=a;i<=b;i++){
		int n=m/i;
		if(m%i==0&&__gcd(i,n)==a){
			ans++;
		}	
	}
	cout<<ans;
	return 0;
} 

然后是之前vp的一些补题QAQ：

扫雷 1

思路

• 这道题用贪心；
• 开一个pair类型的数组，first记录每当前购买价格，second记录当前序号（也就是如果前边没有花钱的话现在理论上有多少钱）；
• 之后对first进行从小到大的排序（默认在first相同情况下，second越小位置越靠前），理论上价格越低，在能购买的范围内最好全买完；
• 定义两个变量，s表示此前花费的雷币总数；ans记录到目前为止买了多少道具；
• 循环中if(c[i].first!=c[i-1].first)的作用是：如果有好几次first相同，在second最大的地方进行购买（此时雷币数最多，能够购买的数量最多）；
• （还有一部分细节放注释里边了QAQ）；

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N=2e5+11;
pair<int,int> c[N];
signed main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		c[i].first=0;
		cin>>c[i].first;
		c[i].second=i;
	}
	sort(c+1,c+n+1);
	int s=0;
	int ans=0;
	for(int i=2;i<=n;i++){
		if(c[i].first!=c[i-1].first){	
			if(c[i-1].second-s<=0)	continue;	//如果钱不够花了就跳过；	
			int tt=(c[i-1].second-s)/c[i-1].first;
			s+=tt*c[i-1].first;
			ans+=tt;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Colorful Segments 2

题目链接

https://codeforces.com/gym/105385/problem/C

思路

• 对左端点进行排序，再对右端点进行排序；
• 按照左端点从小到大进行遍历，每次找这条线段在这之前有多少右端点小于他的线段，这些线段的左端点一定小于当前线段左端点并且一定与该线段不相交；

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N=5e5+10;
int n,k;
int a[N],b[N];

int search_min(int i){
	int l=1,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(b[mid]>=a[i])	r=mid;
		else	l=mid+1;
	}
	return r;
}
signed main()
{
	int t;
	cin>>t;
	while(t--){
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			cin>>a[i]>>b[i];
		}
		sort(a+1,a+n+1);
		sort(b+1,b+n+1);
		int ans=1;
		for(int i=1;i<=n;i++){	
			int t=search_min(i)-1;
//			int t=(lower_bound(b+1,b+n+1,a[i])-(b+1));			
			ans=ans*(k-(i-1-t))%998244353;
		} 
		int m=ans;
		cout<<m<<endl; 
	}
	return 0;
}

ps：也可以把我前边的二分删掉，直接用被我注释掉的lower_bound()函数 QAQ；

Divide the Sequence

题目链接

https://codeforces.com/gym/105385/problem/F

思路

运用后缀和：

• 对后缀和按照从大到小进行排序；
• 相当于每加一次，就是在这个数的前面划一到杠进行分割（）

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=5e5+12;
int s[N],a[N];
bool cmp(int a,int b){
	return a>b;
}
signed main()
{
	int t;cin>>t;
	while(t--){
		int n;cin>>n;		
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=n;i>=1;i--){
			s[i]=s[i+1]+a[i];
		}
		int ans=s[1];
		cout<<ans<<" ";
		sort(s+2,s+n+1,cmp);
		for(int i=2;i<=n;i++){
			ans+=s[i];
			cout<<ans<<" ";
		}
		cout<<endl;
		for(int i=1;i<=n+1;i++){
			s[i]=0;a[i]=0;
		}
	}
	return 0;
}