明明是学深搜的一周，结果这里一道深搜的题解也没有~~
一、洛谷P1082同余方程
题目描述
求关于x xx的同余方程 ax≡1(mod b) 的最小正整数解。
输入格式
一行，包含两个正整数 a,b 用一个空格隔开。
输出格式
一个正整数 x0，即最小正整数解。输入数据保证一定有解。
输入输出样例
输入 #1
3 10输出 #1
7说明/提示
【数据范围】
对于 40%的数据，2≤b≤1,000
对于 60%的数据，2≤b≤50,000,000
对于 100%的数据，2≤a,b≤2,000,000,000
NOIP 2012 提高组 第二天 第一题
解析：
ax≡1(mod b)可以化为ax+by=gcd(a,b)，而ax+by=gcd(a,b)的求解是依赖于拓展欧几里得算法实现的，所以这个题实际上就是在考拓展欧几里得算法，那么，拓展欧几里得算法是什么呢？
我们先来看看欧几里得算法：
欧几里得算法，又称为辗转相除法，是利用gcd(a,b) = gcd(b,a % b)这个原理来计算两个数的最大公因子的算法，代码如下：
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-04-16 20:03:11
* @Website1: https://449293786.site
* @Website2: https://sluowanx.cn
* @原创代码，版权所有，转载请注明原作者
* >> 欧几里得算法 <<
*/
int gcd(int a,int b)
{
while( b> 0)
{
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}而拓展欧几里得算法就是在欧几里得算法上做了一些修改，以用来计算ax+by=gcd(a,b)的结果
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-04-16 20:03:11
* @Website1: https://449293786.site
* @Website2: https://sluowanx.cn
* @原创代码，版权所有，转载请注明原作者
*/
#include <bits/stdc++.h>
typedef long long ll;
ll gcd(ll a,ll b,ll &x,ll &y){
if(!b)
{
x=1;y=0;
return a;
}
ll t=gcd(b,a%b,y,x);
y-=a/b*x;
return t;
}
int main()
{
ll a,b,x,y;
cin>>a>>b;
gcd(a,b,x,y);
cout<<x<<endl;
// cout<<gcd(a,b)<<endl;
// 拓展欧几里得算法同样可以用来求最大公因子
return 0;
}emmm ，如果觉得cpp代码不好理解，这里还有一份Python代码：
'''
@Author: Mr.Sen
@Website1: https://449293786.site
@原创代码，版权所有，转载请注明原作者
'''
def ext_euclid(a, b):
if b == 0:
return 1, 0, a
else:
x, y, q = ext_euclid(b, a % b)
x, y = y, (x - (a // b) * y)
return x, y, q但是上面的代码是过不了的，因为题目要求的是最小正整数，所以我们再后面加b/gcd(a,b)直到变成正整数为止
剩下的大概就看一下这里吧：https://www.cnblogs.com/Mr-WolframsMgcBox/p/7868283.html
反正我也没学拓展欧几里得算法，现学现卖
二、洛谷P1323删数问题
题目描述
一个集合有如下元素：111 是集合元素；若 PPP 是集合的元素，则 2×P+1，4×P+5也是集合的元素。
取出此集合中最小的 k 个元素，按从小到大的顺序组合成一个多位数，现要求从中删除 m 个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。
注：不存在所有数被删除的情况。
输入格式
只有一行两个整数，分别代表 k 和 m。
输出格式
输出为两行两个整数，第一行为删除前的数字，第二行为删除后的数字。
输入输出样例
输入 #1
5 4输出 #1
137915
95说明/提示
数据规模与约定
- 对于 30% 的数据，保证 1≤k,m≤3001
- 对于 100% 的数据，保证 1≤k,m≤3e4
题解：
这个题的解答步骤分为两步：
- 字符串处理
- 贪心选择最大的数（不能用深搜，深搜100亿%超时）
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-04-16 22:45:06
* @Website: https://449293786.site
* @原创代码，版权所有，转载请注明原作者
*/
#include <bits/stdc++.h>
using namespace std;
priority_queue <int,vector<int>,greater<int> > q;
queue <int> wait;
string str(int k)
{
string ans;
q.push(1);
while (k--)
{
//利用优先队列排序
int now=q.top();
q.push(now*2+1);
q.push(now*4+5);
wait.push(now);
q.pop();
}
while(!wait.empty())
{
//将数字转换成字符串
stringstream ss;
ss<<wait.front();
ans+=ss.str();
wait.pop();
}
return ans;
}
int main()
{
int m,k;
cin>>k>>m;
string s=str(k);
cout<<s<<endl;
//贪心
string::iterator it =s.begin();s.insert(it,'9');
int r=0;
int n=s.size();
int sum=0;
int h=1;
while(h<=n&&sum!=m){
if(s[h]<=s[r]){
s[++r]=s[h++];
}
else
r--,sum++;
}
while(h<=n) s[++r]=s[h++];
for(int i=1;i<n-m;i++) cout<<s[i];
cout<<endl;
return 0;
}若未经特殊说明，本文：《 4.12深搜题解 》为博主原创作品，未经授权禁止转载
