蓝桥杯自我复习打卡
总复习，打卡2。二。数论
一，__gcd，lcm
1.最大公约数和最小公倍数标题
关键字：（ lcm, _gcd结论）
https://i-blog.csdnimg.cn/direct/32b83d5aaa5b4d1696f5f17ad47d59d4.png
https://i-blog.csdnimg.cn/direct/8a6881b740a84dc6997445455244149b.png
https://i-blog.csdnimg.cn/direct/499d05e038ba414fa1d3dfe9734b2100.png
AC
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long x0, y0;
cin >> x0 >> y0;
// 1. 如果 y0 不能被 x0 整除，则答案为 0
if (y0 % x0 != 0) {
cout << 0 << "\n";
return 0;
}
// 2. 令 M = y0 / x0
long long M = y0 / x0;
// 3. 计数答案
long long ans = 0;
// 4. 枚举 M 的因数 a
for (long long a = 1; a * a <= M; a++) {
if (M % a == 0) {
long long b = M / a;
// 只有 gcd(a, b) == 1 才满足 gcd(x0*a, x0*b) = x0
if (__gcd(a, b) == 1) {
// 若 a != b，则 (a,b) 和 (b,a) 两对
if (a != b) ans += 2;
// 若 a == b，则只有 1 对
else ans += 1;
}
}
}
cout << ans << "\n";
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll x,y;
cin >> x >> y;
ll count = 0;
// 关键循环：i从x开始，一直到 sqrt(x*y) 为止
for(ll i = x; i <= sqrt(x*y); i++){
// 若 i 正好整除 x*y，则 j = (x*y)/i
// 否则无法组成 (i, j) 使 i*j = x*y
if( (x*y) % i == 0 ){
ll j = (x*y) / i;
// 计算 gcd(i, j)
ll yueshu = __gcd(i, j);
// 条件1：gcd(P,Q) = x=>gcd(i,j) = x
// 条件2：P*Q = x*y (用来保证 lcm(P,Q) = y 也满足)
// 上面第2条已经用 (x*y)%i == 0 来保证
if( yueshu == x ){
// 如果 i == j，则只算1个 (因为 (i,j) == (j,i))
// 如果 i != j，则算2个 (因为 (i,j) 和 (j,i) 是两种)
if(i * i == x*y){
count += 1;
}
else{
count += 2;
}
}
}
}
cout << count;
return 0;
}
https://i-blog.csdnimg.cn/direct/199f5a1c86cb47c59a2e4c4f680217a6.png
https://i-blog.csdnimg.cn/direct/75e25eed215647b7b0d1a175d69043dc.png
https://i-blog.csdnimg.cn/direct/ff0ad4a3247a42bda644298b792d36ac.png
https://i-blog.csdnimg.cn/direct/15339233491c493ba806613d6d571274.png
2.最大公约数
关键字：（曼哈顿间隔，bfs）
https://i-blog.csdnimg.cn/direct/702240f0ecfe47f0b3f182fae213fa63.png
https://i-blog.csdnimg.cn/direct/eb0621f14c25498fa97b79e63637bc15.png
曼哈顿间隔。
https://i-blog.csdnimg.cn/direct/9af56c1b0a9f41b19b6f657c1e108d94.png
https://i-blog.csdnimg.cn/direct/5f1e5a3633e247e2afdb593bf9209aa7.png
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=2e3+10;
LL a,d; //两个数组要开long long类型，数组d要开为 n+m 的最大值
LL GCD(LL a,LL b)
{
LL c=0;
while((c=a%b))
{
a=b;
b=c;
}
return b;
}
int main()
{
int n,m,x,y;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a;
cin>>x>>y;
if(a==1)
{
cout<<0;
return 0;
}
for(int i=0;i<=n+m;i++)
d=a;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(i!=x||j!=y) //注意需要排除自身
{
int dis=abs(x-i)+abs(y-j);
d=GCD(a,d);
}
for(int i=1;i<=n+m;i++)
{
d=GCD(d,d);
if(d==1)
{
cout<<i;
return 0; //提前结束程序
}
}
cout<<-1;
return 0;
} bfs
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
ll x,y,val;
};
node mp;
ll vis;
ll dx[]={-1,1,0,0};
ll dy[]={0,0,-1,1};
ll ans=0;
ll x,y;
ll n,m;
void bfs(){
queue<node> q;
queue<ll> steps;
q.push({x,y,mp.val});
steps.push(0);
ll yueshu=mp.val;
vis=1;
while(!q.empty()){
node top=q.front();q.pop();
ll step=steps.front();steps.pop();
for(ll i=0;i<4;i++){
ll nx=top.x+dx;
ll ny=top.y+dy;
ll value=mp.val;
if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
if(!vis){
yueshu=__gcd(yueshu,value);
vis=1;
q.push({nx,ny,value});
steps.push(step+1);
if(yueshu==1){
cout<<step+1<<'\n';
return;
}
}
}
}
cout<<-1;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
cin>>mp.val;
}
}
cin>>x>>y;
if(mp.val==1){
cout<<0;
return 0;
}
bfs();
return 0;
} 3.斐波那契公约数
关键字：（鸽巢原理，黄金分割比，矩阵快速幂）
https://i-blog.csdnimg.cn/direct/050099af07df4322bc2bc7cea205110f.png
。。。前面那么多斐波那契数，纸上摆列一下，相邻两对最大公约数 基本都是1，直接暴力输出1，一个测试点也没过。。由于标题问的是恣意两个斐波那契数的最大公因数。
打个表看看规律。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e8;
ll n,m;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
ll a;
a=0,a=1;
for(ll i=2;i<50;i++){
a=a+a;
}
for(ll i=1;i<=49;i++){
for(ll j=1;j<=49;j++){
if(i!=j){
cout<<a<<""<<a<<"";
cout<<__gcd(a,a)%N<<'\n';
}
}
}
return 0;
} https://i-blog.csdnimg.cn/direct/c26ce73f43a04813a3fda65ea2b60fc2.png
https://i-blog.csdnimg.cn/direct/f0df58ff8acc475eaf20ad815517501e.png
大部分是1，大概来那个数中较小的那个，很少别的数字。
大佬解法：
https://i-blog.csdnimg.cn/direct/2cf02598f965470392635a1235be086b.png
https://i-blog.csdnimg.cn/direct/fb0c44e6d3844b53b5ed2162dff54a5b.png
https://i-blog.csdnimg.cn/direct/6c12e74d4ad244948fa9e88db17e367b.png
https://i-blog.csdnimg.cn/direct/d1a93f4ce0c543e7b5ab93de477a0ae2.png
https://i-blog.csdnimg.cn/direct/d9d84bb3e3ad49db91868c41c369d848.png
https://i-blog.csdnimg.cn/direct/29f40c23baba4cb399af44a7c89cb8d2.png
https://i-blog.csdnimg.cn/direct/839e1af1be3e41518e1334a3050dabd0.png
https://i-blog.csdnimg.cn/direct/32f6d8224d7f48ec86ec69292891d110.png
代码思路捋一下，其实就是，我们想求__gcd(f，f)，根据斐波那契数列性子可以知道，__gcd(f，f）=f(__gcd(n,m))，以是标题转化为了求 f(__gcd(n,m))，看标题数据范围，1≤n,m≤109。假如单纯的递归求f(__gcd(n,m))，标题也很复杂，我们就想到了使用这个递推关系，构建一个关系矩阵，递推发现 f(__gcd(n,m)) = （关系矩阵）^n * 矩阵（{0,1}），标题就更进一步的简化了，我们只用求关系矩阵的n次方即可。标题迎刃而解。
注意：直接暴力算关系矩阵的n次方还是会超时，必须得用矩阵快速幂。
#include <iostream>
#include <numeric>// for gcd
using namespace std;
typedef long long ll;
const ll MOD = 100000000;// 10^8
// 定义 2x2 矩阵结构体
struct Matrix {
ll m;
};
// 矩阵乘法（2x2 矩阵），结果取模 MOD
Matrix multiply(const Matrix &A, const Matrix &B) {
Matrix C;
C.m = (A.m * B.m + A.m * B.m) % MOD;
C.m = (A.m * B.m + A.m * B.m) % MOD;
C.m = (A.m * B.m + A.m * B.m) % MOD;
C.m = (A.m * B.m + A.m * B.m) % MOD;
return C;
}
// 矩阵快速幂，计算 base^exp
Matrix matrixPower(Matrix base, ll exp) {
// 初始化单位矩阵
Matrix result = {{{1, 0}, {0, 1}}};
while(exp > 0) {
if(exp & 1) {
result = multiply(result, base);
}
base = multiply(base, base);
exp >>= 1;// exp 除以 2
}
return result;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, m;
cin >> n >> m;
// 利用性质: gcd(f(n), f(m)) = f(gcd(n, m))
ll d = std::gcd(n, m);
// 斐波那契转换矩阵 T = [,]
Matrix T = {{{0, 1}, {1, 1}}};
// 计算 T^d
Matrix T_d = matrixPower(T, d);
// 根据性质：
// T^d = [ , ]
// 所以 f(d) 就是 T^d
cout << T_d.m % MOD << "\n";
return 0;
}
https://i-blog.csdnimg.cn/direct/f18cb7b603854780940ae7a9c23ecace.png https://i-blog.csdnimg.cn/direct/d2bb936bea59414b80cb4874df7f069d.png
这鸽巢原理，直接省去好大的麻烦，我就说数学学好很有用吧！nnnnnnnnnnb！
https://i-blog.csdnimg.cn/direct/1e61377c33394d91b023f93757696ef8.png
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e8;
ll n,m;
ll f;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
n=__gcd(n,m);
f=1;
f=1;
if(n>150000000)n%=150000000;
for(ll i=3;i<=n;i++){
f=(f[(i-1)%3]%N)+(f[(i-2)%3]%N);
}
cout<<f%N;
return 0;
} https://i-blog.csdnimg.cn/direct/8ff5efffe53c44059bc15601eb48d126.pnghttps://i-blog.csdnimg.cn/direct/5c64524644ef48b6a75e29e9e9154150.png
https://i-blog.csdnimg.cn/direct/9be388cba3404935b000d262a418f9ab.png
https://i-blog.csdnimg.cn/direct/2081119d8b1d446ca696bddb34648999.png
4.因子和
关键字：（质因数分解，快速幂，费马小定理，分治思想）
https://i-blog.csdnimg.cn/direct/03737dfb15c5433bbada5af6af915806.png
这个标题不要试图先求a^b，由于当a,b,都趋近5*1e7时，得到的结果远远超过long long ,即使用字符串处理惩罚也会丢失精度，超时。以是可以先从a分解入手，化简发现一个式子，再使用费马小定理结合快速幂即可解题。
https://i-blog.csdnimg.cn/direct/e31caaf29c9e45bfa076ddd177678ebd.png
https://i-blog.csdnimg.cn/direct/71b1b86f28e94840ae4dfd0528e5ab06.png
https://i-blog.csdnimg.cn/direct/4541f431351d4fa69d216f1562f26388.png
https://i-blog.csdnimg.cn/direct/62e92fad6492404ea135c32915ebcdd7.png
https://i-blog.csdnimg.cn/direct/f036cf593b1b461f8228f87b75f6ce07.png
https://i-blog.csdnimg.cn/direct/194863491acb4b93b26f4d53de01d495.png
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
ll qsm(ll a,ll b){
ll res=1;
a%=9901;
while(b){
if(b&1)res=(res*a)%9901;
a=a%9901*a%9901;
b>>=1;
}
return res%9901;
}
ll sum(ll base,ll zhishu){
if(base%9901==1){
return (zhishu*b+1)%9901;
}else{
ll cur1=(qsm(base,zhishu*b+1)-1)%9901;
if(cur1<0)cur1+=9901;//要加上这个判断不然会有一个测试点过不了
ll cur2=qsm((base-1)%9901,9901-2);
if(cur2<0)cur2+=9901;
return cur1 %9901 *cur2 %9901;
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>a>>b;
ll res=1;
ll t=a;
for(ll i=2;i*i<=t;i++){
ll cnt=0;
while(t%i==0){
cnt++;
t/=i;
}
res=(res %9901 *sum(i,cnt))%9901;
//别写res*=(sum(i,cnt))%9901不然容易爆，会有一个测试点不补了
}
if(t!=1){
res=(res*sum(t,1))%9901;
}
cout<<res%9901;
return 0;
}
/*
a = p1^x1 * p2^x2 * p3^x3 * ....pk^xk;
a^b = (p1^x1 * p2^x2 * p3^x3 * ....pk^xk)^b;
a^b = (p1^(x1*b) * (p2^(x2*b)) * .....(pk^(xk*b));
a^b = (p1^1 + p1^2 +.....p1^(x1*b)) * (p2^1 + p2^2 + .....p2^(xk*b)).....
if( (p1^(x1*b) %9901 ==1){//等于0时没意义
a^b = (1+1+1....) * (1+1....) *....
a^b = (x1*b+1)*1*(x2*b+1)....
}
else 老老实实算
a^b = ( (p1^(x1*b) - 1) / (p1 - 1) ) % 9901 * ( (p2^(x2*b) - 1) / (p2 - 1) ) % 9901.....
a^b = ( (p1^(x1*b) - 1) * (p1-1)^(-1) ) %9901 *.....
*/ #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 9901;
ll a, b;
// 快速幂（计算 a^b mod mod）
ll qsm(ll a, ll b) {
ll res = 1;
a %= mod;
while(b) {
if(b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
// 计算几何级数和：1 + p^b + p^(2b) + ... + p^(e*b)
// e 为 a 中 p 的指数，即 a^b 中 p 的指数为 e*b
ll sum(ll p, ll e) {
ll exp_total = e * b; // a^b 中 p 的最高指数
// 如果 p ≡ 1 (mod mod)，则 p^j ≡ 1，和就是 (exp_total+1)
if(p % mod == 1) {
return (exp_total + 1) % mod;
} else {
// 根据等比数列求和公式：
// S = (p^(exp_total+1) - 1) / (p - 1) mod mod
ll numerator = (qsm(p, exp_total + 1) - 1) % mod;
if(numerator < 0) numerator += mod;
ll denominator = (p - 1) % mod;
if(denominator < 0) denominator += mod;
// 利用费马小定理求模逆元 (mod 为质数)
ll invdenom = qsm(denominator, mod - 2);
return (numerator * invdenom) % mod;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> a >> b;
ll res = 1;
ll tmp = a;
// 质因数分解
for(ll i = 2; i * i <= tmp; i++){
if(tmp % i == 0){
ll cnt = 0;
while(tmp % i == 0){
cnt++;
tmp /= i;
}
res = (res * sum(i, cnt)) % mod;
}
}
// 如果 tmp 不为 1，则剩余 tmp 为质因子
if(tmp != 1) {
res = (res * sum(tmp, 1)) % mod;
}
cout << res % mod << "\n";
return 0;
}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,ans=1,mod=9901;
ll ksm(ll x,ll y){//快速幂
ll res=1;
while(y){
if(y%2==1)res=res*x%mod;
x=x*x%mod;
y/=2;
}
return res;
}
ll sum(ll x,ll y){//等比数列和
if(x==0)return 1;
if(x%2==1)return sum(x/2,y)*(1+ksm(y,x/2+1))%mod;
//偶数项，分两部分算（后半就是前半乘y^(x/2+1)）
return (sum(x/2-1,y)*(1+ksm(y,x/2+1))+ksm(y,x/2))%mod;
//奇数项，加上中间一项
//因算了y^0，所以x%2==1是偶数项
}
int main (){
cin>>a>>b;
for(int i=2;i<=sqrt(a);i++){//质因数分解
int c=0;
while(a%i==0){
a/=i;
c++;
}
ans=ans*sum(c*b,i)%mod;
}
if(a!=1)
ans=ans*sum(b,a)%mod;
cout<<ans;
} 5. 最大公约数
关键字：（稀疏表，二分查找，线段树）
https://i-blog.csdnimg.cn/direct/8040ff79e7344180a07ef0b4fff8650e.png
AC（稀疏表）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 求两个数的最大公约数
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; i++){
cin >> a;
}
// 如果数组中已有 1，直接把其他数字“变为 1”
int ones = 0;
for (int i = 0; i < n; i++){
if(a == 1) ones++;
}
if(ones > 0){
cout << (n - ones) << "\n";
return 0;
}
// 检查整个数组的 gcd，如果大于 1，则永远无法生成 1
ll overall = a;
for (int i = 1; i < n; i++){
overall = gcd(overall, a);
}
if(overall > 1){
cout << -1 << "\n";
return 0;
}
// 数组中没有 1 且整体 gcd 为 1，则一定存在某个子区间的 gcd 为 1
// 利用稀疏表快速查询任一区间的 gcd
int logn = floor(log2(n)) + 1;
vector<vector<ll>> st(n, vector<ll>(logn, 0));
for (int i = 0; i < n; i++){
st = a;
}
for (int j = 1; j < logn; j++){
for (int i = 0; i + (1 << j) - 1 < n; i++){
st = gcd(st, st);
}
}
// 预处理 logs 数组，方便查询
vector<int> logs(n+1);
logs = 0;
for (int i = 2; i <= n; i++){
logs = logs + 1;
}
// lambda 函数，快速查询区间 内的 gcd
auto query = [&](int L, int R) -> ll {
int j = logs;
return gcd(st, st);
};
// 枚举每个起点，利用二分查找找出最短区间长度使得 gcd=1
int best = INT_MAX;
for (int i = 0; i < n; i++){
int lo = i, hi = n - 1, pos = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(query(i, mid) == 1){
pos = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
if(pos != -1){
best = min(best, pos - i);
}
}
// 先需要 (best) 次操作在某个位置“制造出” 1（实际上是 best 次操作把那个区间变为 1，注意原代码中是 (L-1) 次操作，
// 这里由于我们用的是区间长度差值 pos-i，所以总操作数为 best + (n - 1)）
cout << best + (n - 1) << "\n";
return 0;
}
非AC
https://i-blog.csdnimg.cn/direct/fabf39e0adb4431698d54bdfdf198fd8.png
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
// 单独讨论 n == 1 的情况
if(n == 1){
ll x;
cin >> x;
cout << (x == 1 ? 0 : -1) << "\n";
return 0;
}
vector<ll> a(n);
bool hasOne = false;
for(ll i = 0; i < n; i++){
cin >> a;
if(a == 1) hasOne = true;
}
// 如果数组中已有1，则直接将所有非1转变为1，每个非1只需一次操作
if(hasOne){
ll cnt = 0;
for(ll i = 0; i < n; i++){
if(a != 1) cnt++;
}
cout << cnt << "\n";
return 0;
}
// 如果所有元素都相同，则无法变成全1（因为此时不可能通过 gcd 操作出现1）
set<ll> s(a.begin(), a.end());
if(s.size() == 1){
cout << -1 << "\n";
return 0;
}
/*
以下思路：
- 数组全为偶数时无法通过相邻操作得到1（因为偶数 gcd 偶数仍为偶数）。
- 只要有奇数，则有可能通过操作把某个数变成1。
- 如果有两个以上奇数，根据你的思路直接输出 n（认为最少操作次数为 n）。
- 如果只有1个奇数，则尝试与相邻元素通过反复 gcd 得到1，
然后用得到的1扩散到整个数组（每个非1需要一次操作）。
*/
ll oddCount = 0;
for(ll i = 0; i < n; i++){
if(a & 1) oddCount++;
}
// 若全为偶数，则无法得到1
if(oddCount == 0){
cout << -1 << "\n";
return 0;
}
// 当奇数个数大于等于2时，根据你的注释直接输出 n
if(oddCount >= 2){
cout << n << "\n";
return 0;
}
// 下面处理奇数个数恰好为1的情况
ll idx = -1;
for(ll i = 0; i < n; i++){
if(a & 1){
idx = i;
break;
}
}
// 使用 _gcd 替换 std::gcd（在 <algorithm> 中提供）
if(idx == 0){
if(__gcd(a, a) == 1){
cout << n << "\n";
} else {
ll cnt = 0;
while(__gcd(a, a) != 1){
cnt++;
a = __gcd(a, a);
}
cout << cnt + (n - 1) << "\n";
}
}
else if(idx == n - 1){
if(__gcd(a, a) == 1){
cout << n << "\n";
} else {
ll cnt = 0;
while(__gcd(a, a) != 1){
cnt++;
a = __gcd(a, a);
}
cout << cnt + (n - 1) << "\n";
}
}
else{
// idx 在中间位置，取其相邻两个数中的较小值作为参考
ll neighbor = min(a, a);
if(__gcd(a, neighbor) == 1){
cout << n << "\n";
} else {
ll cnt = 0;
while(__gcd(a, neighbor) != 1){
cnt++;
a = __gcd(a, neighbor);
}
cout << cnt + (n - 1) << "\n";
}
}
return 0;
}
https://i-blog.csdnimg.cn/direct/af8abf7497bb4b05b40676c3606e1ffe.png
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n;cin>>n;
ll a;
ll ones=0;
for(ll i=0;i<n;i++){
cin>>a;
if(a==1)ones++;
}
if(ones>0){
cout<<n-ones<<'\n';
return 0;
}
/*
数字全都一样变不了。
全为偶数变不了。
检查整个数组的 gcd，如果大于 1，则永远无法生成 1
只要有1个1，必然可以变，先找一对类似4 6的组合
变成2 3然后就可以获得一个1了，有一个1，剩下的1个数需要1次操作即可
有两个以上的奇数的，先选择奇奇组合，奇偶组合
找最小的奇数（不，对管他多大，反正都可以直接变成1，）和其相邻的最小的偶数组合在一起变小,
谁的相邻偶数小，就选谁
*/
ll gongyueshu=a;
for(ll i=1;i<n;i++) gongyueshu=__gcd(gongyueshu,a);
if(gongyueshu>1){
cout<<-1;
return 0;
}
ll ans=1e9;
for(ll i=0;i<n;i++){
ll x=a,cnt=0;
for(ll j=i+1;j<n;j++){
cnt++;
x=__gcd(x,a);
if(x==1){
ans=min(ans,cnt);
break;
}
}
}
if(ans==1e9)cout<<-1;
else cout<<n+ans-1;
return 0;
} AC
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 求最大公约数
ll _gcd(ll a, ll b) {
return b == 0 ? a : _gcd(b, a % b);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for(int i = 0; i < n; i++){
cin >> a;
}
// 如果数组中已有 1，则直接用“扩散”操作：
int ones = 0;
for (int i = 0; i < n; i++){
if(a == 1)
ones++;
}
if(ones > 0){
cout << (n - ones) << "\n";
return 0;
}
// 检查整个数组的 gcd 是否为1
ll overall = a;
for (int i = 1; i < n; i++){
overall = _gcd(overall, a);
}
if(overall > 1){
cout << -1 << "\n";
return 0;
}
// dp 用来维护所有以当前位置结尾的区间的 gcd 及其最短区间长度
// 每个元素为 {g, len}，表示：某个子区间的 gcd 为 g，长度为 len
vector<pair<ll,int>> dp;
int best = INT_MAX; // 最短区间长度使得 gcd==1
for (int i = 0; i < n; i++){
vector<pair<ll,int>> ndp;
// 新区间：仅包含 a
ndp.push_back({a, 1});
// 将前面 dp 中的所有区间与 a 合并
for (auto &p : dp) {
ll newg = _gcd(p.first, a);
int newlen = p.second + 1;
// 如果 ndp 最后一个元素与 newg 相同，则保留较短的长度
if(!ndp.empty() && ndp.back().first == newg) {
ndp.back().second = min(ndp.back().second, newlen);
} else {
ndp.push_back({newg, newlen});
}
}
// 更新答案：若存在 gcd==1 的子区间，记录其长度
for(auto &p : ndp) {
if(p.first == 1) {
best = min(best, p.second);
}
}
dp = ndp;
}
// 根据题意：先在某个位置用 (L - 1) 次操作制造出 1，
// 然后用 (n - 1) 次操作将1扩散到整个数组。
// 注意 L 为最短子区间长度（best）
int ans = (best - 1) + (n - 1);
cout << ans << "\n";
return 0;
}
二，快速幂，费马小定理
1.矩阵快速幂（模版题）
关键字：（矩阵快速幂）
https://i-blog.csdnimg.cn/direct/16b00c6d012d4b89aaa9f259de961d27.png
https://i-blog.csdnimg.cn/direct/11d0e6101e1544de8175050f395bfaf0.png
https://i-blog.csdnimg.cn/direct/85fd3f234f23427290d74dfddd4a725a.png
https://i-blog.csdnimg.cn/direct/31d9eb00706841c6ba52f1ac67a92a2f.png
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e9+7;
typedef vector<vector<ll>> vec;
// 假设矩阵是 n x n（1-index化），因此实际数组大小是 n+1 x n+1
vec juzhen_mul(const vec &A, const vec &B) {
/*
ll n = A.size();
vec C(n, vector<ll>(n, 0));
这么写会runtime error
*/
ll n = A.size()-1;
vec C(n+1, vector<ll>(n+1, 0));
for (int i = 1; i <= n; i++){
for (int k = 1; k <= n; k++){
// 提前计算 A，可以减少重复访问
ll temp = A;
for (int j = 1; j <= n; j++){
C = (C + temp * B) % N;
}
}
}
return C;
}
vec qsm(vec x,ll k,ll n){
vec res(n+1,vector<ll>(n+1,0));
for(ll i=1;i<=n;i++){
res=1;
}
while(k){
if(k&1)res=juzhen_mul(res,x);
x=juzhen_mul(x,x);
k>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,k;cin>>n>>k;
vec mp(n+1,vector<ll>(n+1,0));
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++){
cin>>mp;
mp=mp%N;
if(mp<0)mp+=N;
}
}
//for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)cout<<mp<<'\n';
vec ans=qsm(mp,k,n);
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++){
cout<<ans%N<<" ";
}
cout<<'\n';
}
return 0;
}
2.高精小数幂
关键字：（高精度，快速幂）
https://i-blog.csdnimg.cn/direct/2a40189ead9648499e9ab0248d563bcc.png
抛开小数不谈，本题求a^n，由于数字较大，要用到高精算法，n的值不大，可以不消快速幂。
本题a可能是小数，可以如许解决，先记载a的小数位数pt，并将a乘以10^pt，转化为整数a′，求出a′^n，设为s′，答案即是s′/(10×pt×n)，即输出时将s′的末尾pt×n位作为小数输出即可。
例：求1.25^2，先求125^2，即是15625，由于1.25有两位小数，1.25^2就有4位小数，所有用果即是1.5625。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1300; //100000^250有1250位
int pt;
struct Bign{
int s, len;
Bign(int num = 0){
memset(s, 0, sizeof(s));
len = 1;
s = num;
}
Bign operator * (int b)const{
Bign c;
c.len = len + 10;
for (int i = 1; i <= c.len; i++){
c.s += s * b;
c.s = c.s / 10;
c.s %= 10;
}
c.clean();
return c;
}
void clean(){
while (len > 1 && !s) len--;
}
};
ostream& operator << (ostream &out, const Bign &x){
int i;
for (i = x.len; i > 0 && i > pt; i--) //输出整数部分
out << x.s;
if (i){ //若i不为0，表示还有小数部分
out << "."; //先输出"."
for (i = pt; i > 0; i--) //再输出小数部分
out << x.s;
}
return out;
}
int main(){
double a;
int n;
while (cin >> a >> n){
//求a的小数位数
pt = 0; //pt记录a的小数位数
while (fabs(a - round(a)) > 1e-6){ //若a不等于a的整数部分，表示a不是整数
pt++; //小数位数加一位
a *= 10;
}
pt *= n; //a^n的小数位数等于a的小数位数 ×n
//求s = a ^ n
Bign s = 1;
for (int i = 1; i <= n; i++)
s = s * (int)round(a);
cout << s << endl;
}
return 0;
} 这题不发起用快速幂，否则不太轻易调试的，而且比力冗长，直接模拟就好了。
https://i-blog.csdnimg.cn/direct/f7007799b55c4c05869918fc3e77f5bb.png
https://i-blog.csdnimg.cn/direct/ef7974a0b157496686361f326ccab5d4.png
这也是c下标是k+j缘故原由。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 全局定义，和原C代码一致，只是将 int 改成 long long
// 存放每位数字的数组 a[], b[], c[] 以及输入字符串 s[]
ll a, b, c;
char s;
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
string s;ll n;
while (cin>>s>>n) {
// 1) 初始化
memset(a, 0, sizeof(a));
ll t = 0; // 记录整数部分位数
ll flag = 0; // 判断是否有小数点
ll len = s.length();
// 2) 找到小数点位置
ll i, j, k;
size_t pos = s.find('.');
if (pos != string::npos) {
t = pos; // 小数点前的数字个数
len--; // 去掉小数点后长度减1
// 将小数点后面的字符向前移动覆盖小数点
for (j = pos; j < s.length(); j++) {
s = s;
}
} else {
t = len;
}
// 4) 计算最终要保留的小数位数 point = (原小数位数)×n
// (原小数位数) = (len - t)
ll point = (len - t) * n;
// 5) 把去掉 '.' 后的数字逆序存到 a[]，a是最低位
for (i = 0; i < len; i++) {
a = (s - '0'); // 字符转数字
}
// 6) 用 b[] 表示累乘结果，初值为 1
memset(b, 0, sizeof(b));
b = 1;
ll len1 = 1; // b[]当前的有效位数
// 7) 计算 a^n：重复乘法
for (i = 1; i <= n; i++) {
memset(c, 0, sizeof(c));
// 竖式乘法：b×a => c
for (j = 0; j < len; j++) {
for (k = 0; k < len1; k++) {
c += a * b;
}
}
// 处理进位
for (k = 0; k < len + len1; k++) {
c += c / 10;
c %= 10;
}
// 拷贝结果回 b[]
memcpy(b, c, sizeof(c));
// 更新 b 的长度
len1 += len;
}
// 8) 去掉最高位多余 0
while (b == 0 && len1 > 0) {
len1--;
}
// 9) 输出：先输出整数部分 b
// (当 point>len1 时，可能只输出几个数字或为 0)
for (i = len1; i >= point; i--) {
cout << b;
}
// 10) 判断小数部分是否全为0，如果不是，就输出
for (i = 0; i < point; i++) {
if (b != 0) {
break;
}
}
// 如果小数部分有非零，则输出
if (i < point) {
cout << ".";
for (ll j = point - 1; j >= i; j--) {
cout << b;
}
}
cout << "\n";
}
return 0;
} #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;
char s;
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
string s;ll n;
while (cin>>s>>n){
ll len=s.length();
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
size_t idx=s.find('.');
ll t=0;
if(idx!=string::npos){
t=idx;
len--;
for(ll i=idx;i<s.length();i++)s=s;
}else t=len;
ll point=(len-t)*n;
for(ll i=0;i<len;i++)a=s-'0';
b=1;
ll len1=1;
for(ll i=1;i<=n;i++){
memset(c,0,sizeof(c));
for(ll j=0;j<len;j++){
for(ll k=0;k<len1;k++){
c+=a*b;
}
}
for(ll j=0;j<len1+len;j++){
c+=c/10;
c%=10;
}
memcpy(b,c,sizeof(c));
len1+=len;
}
while(b==0&&len1>0)len1--;
ll i=len1;
for(i=len1;i>=point;i--)cout<<b;
//if(idx!=string::npos)cout<<'.';
for(i=0;i<point;i++){//注意下标的使用，这里用i，还能保证直接对后面的i<point进行判断
if(b!=0){
break;
}
}
if(i<point){
cout<<'.';
for(ll j=point-1;j>=i;j--)cout<<b;
}
cout<<'\n';
}
return 0;
}
3.小猫
关键字：（快速幂，卡特兰数）
https://i-blog.csdnimg.cn/direct/cd7876244ed142edbe8cb8a8d38f448a.png
https://i-blog.csdnimg.cn/direct/e8fe794def9f48679654757f781d8155.png
https://i-blog.csdnimg.cn/direct/c7f9e5bfa65140448d53bec6cddf680f.png
https://i-blog.csdnimg.cn/direct/b4533e3da85647bd920a55ff8b4c4b33.png
https://i-blog.csdnimg.cn/direct/9d1e17a609e744b5b0c087927b3203b1.png
https://i-blog.csdnimg.cn/direct/08d409df95cd4fbe9485853e0a234fb9.png
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e9+7;
ll qsc(ll a,ll b){
a%=N;b%=N;
ll c=(a%N *b%N)/N;
ll ans=a*b-c*N;
if(ans<0)ans+=N;
else ans-=N;
return ans;
}
ll qsm(ll a,ll b){
ll res=1;
a%=N;
while(b){
if(b&1)res=(res%N*a%N)%N;
a=(a%N*a%N)%N;
b>>=1;
}
return res%N;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n;cin>>n;
ll ans1=1,ans2=1,ans3=1;
for(ll i=1;i<=2*n;i++){
if(i<=n)ans1=qsc(ans1,i)%N;
if(i<=n+1)ans2=qsc(ans2,i)%N;
ans3=qsc(ans3,i)%N;
}
ll ans4=qsm(qsc(ans1,ans2),N-2);
ll final=qsc(ans3,ans4);
cout<<final%N;
return 0;
}
/*
也就是求（2*n)! / (n)! *(n+1)!
*/
4.模意义下的乘法逆元
关键字：（快速幂，费马小定理，拓展欧几里得算法）
https://i-blog.csdnimg.cn/direct/96d95c173c2545519340390ac81aeefa.png
https://i-blog.csdnimg.cn/direct/2373c617656b44edb44600d69d2120c2.png 非AC
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qsm(ll a,ll b,ll p){
ll res=1;
while(b){
if(b&1)res=res%p*a%p;
a=a%p*a%p;
b>>=1;
}
return res%p;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,p;cin>>n>>p;
for(ll i=1;i<=n;i++){
cout<<qsm(i,p-2,p)%p<<'\n';
}
return 0;
} AC
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qsm(ll a,ll b,ll p){
ll res=1;
while(b){
if(b&1)res=res%p*a%p;
a=a%p*a%p;
b>>=1;
}
return res%p;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,p;cin>>n>>p;
ll c;//存储阶乘
c=1;
for(ll i=1;i<=n;i++){
c=c*i%p;
}
ll ans;//存答案
ll pow=(qsm(c,p-2,p))%p;//要有这步，不然后面重复计算会超时
ll k=0;
for(ll i=n;i>=1;i--){
k=(pow*i)%p;//变成了（n-1)!的逆元了。
ans=pow %p *c%p;
pow=k;
}
for(ll i=1;i<=n;i++)cout<<ans%p<<'\n';
return 0;
} https://i-blog.csdnimg.cn/direct/4c9b2179e8444ef09ed96622bc318fac.png
AC
#include <iostream>
#include <vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, p;
cin >> n >> p;
// 存储 1~n 的逆元，注意题目要求 1≤n<p
vector<int> inv(n + 1, 0);
inv = 1;
for (int i = 2; i <= n; i++){
// 根据公式：inv = (p - (p / i)) * inv mod p
inv = (int)((long long)(p - p / i) * inv % p);
}
for (int i = 1; i <= n; i++){
cout << inv << "\n";
}
return 0;
}
AC
#include <stdio.h>
char pc_buf, *pc_p= pc_buf;
#define pc(c) *pc_p++= c;
void write(int x) {
static int sta;
register int top= 0;
do { sta[++top]= x % 10, x/= 10; } while(x);
while(top) pc(sta ^ 48);
}
int inv(int a,int m){
register int x=1,y=0,q=0,mod=m;
while(1){
if(m) y-=q*x,q=a/m,a-=q*m;
else return a==1? (x<0? (x+mod)%mod : x) : 0;
if(a) x-=q*y,q=m/a,m-=q*a;
else return m==1? (y<0? (y+mod)%mod : y) : 0;
}
}
int main(){
int n,p;
scanf("%d %d",&n,&p);
for(register int i=1;i<=n;i++)
write(inv(i,p)),pc('\n');
fwrite(pc_buf,1,pc_p-pc_buf,stdout);
return 0;
} https://i-blog.csdnimg.cn/direct/789dea63411441d08f76df473ef30bc5.png
5.因子和（同上4.因子和）
三，线性筛，埃拉筛，质因数分解
1.线性筛素数（模版题）
关键字：（线性筛，埃拉筛）
https://i-blog.csdnimg.cn/direct/c7f2b2d9a1af4ae79825d44e4328a420.png
埃拉托色尼筛法
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
// 使用 bitset 存储 的标记（n=1e8时需要 100,000,001 位，约 12.5 MB 内存）
bitset<100000001> isPrime;
isPrime.set();// 所有位置1（初始假设都是素数）
isPrime = isPrime = 0;// 0 和 1 不是素数
int limit = sqrt(n) + 1;
for (int i = 2; i <= limit; i++){
if (isPrime){
// 从 i*i 开始标记，步长为 i
for (long long j = (long long)i * i; j <= n; j += i)
isPrime = 0;
}
}
// 收集所有素数到 vector 中
vector<int> primes;
// 预留足够空间（n=1e8内大约有 5~6 百万素数）
primes.reserve(6000000);
for (int i = 2; i <= n; i++){
if (isPrime)
primes.push_back(i);
}
// 对于每个查询，输出第 k 小的素数（k 从1开始计数）
while(q--){
int k;
cin >> k;
cout << primes << "\n";
}
return 0;
}
线性筛
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
// 使用 vector<bool> 存储标记，空间约 n+1 位（n=1e8约 12.5 MB）
vector<bool> isComposite(n+1, false);
vector<int> primes;
// 预估预留空间（质数数量大约在 5~6 百万左右）
primes.reserve(n / 10);
for (int i = 2; i <= n; i++){
if (!isComposite)
primes.push_back(i);
for (int j = 0; j < (int)primes.size() && (long long)primes * i <= n; j++){
isComposite * i] = true;
if (i % primes == 0)
break;
}
}
// 回答每个查询，输出第 k 小的素数（k 从 1 开始）
while(q--){
int k;
cin >> k;
cout << primes << "\n";
}
return 0;
}
我服了。。。。。风俗性用typedef long long ll;结果一直MLE，到底不知道咋回事的，结果我改成了typedef int ll.就过了。。。。。。
https://i-blog.csdnimg.cn/direct/261c11d191fb471e982804876ab27d91.png
https://i-blog.csdnimg.cn/direct/354093ad9553435c88a24994ed1fa3e2.png
https://i-blog.csdnimg.cn/direct/bf210fdaeaca4926b517391724cdee89.png
2. 回文质数 Prime Palindromes
关键字（线性筛，埃拉筛，MLE）
https://i-blog.csdnimg.cn/direct/6c865979db29488ebc63ec4c8499e62c.png
又又又又MMMMMMMMMLLLLLLLLLLLLEEEEEEEEE。。。。。不外又让我知道里一个细节点，有时间内存轻易超限的题少开long long ，用bool比用int来表现vis数组内存开销更小，bitset最小。
埃拉筛。
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll a,b;cin>>a>>b;
vector<bool> vis(b+1,1);///用int最后一个测试点还是会MLE
for(ll i=0;i<=b;i++)vis=1;
for(ll i=2;i<=sqrt(b)+1;i++){
if(vis==1){
for(long long j=1LL*i*i;j<=b;j+=i){
vis=0;
}
}
}
for(ll i=a;i<=b;i++){
if(vis==1){
string x=to_string(i);
string y=x;
reverse(x.begin(),x.end());
if(x==y)cout<<y<<'\n';
}
}
return 0;
} #include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 读入区间
int a, b;
cin >> a >> b;
// 建立一个 bitset 标记是否为“可能是素数”
// 下标范围 ，前提: b <= 1e8
static bitset<100000001> isPrime;
isPrime.set(); // 初始全设为 1（可能是素数）
isPrime = 0; // 0 不是素数
isPrime = 0; // 1 不是素数
// 1) 用埃拉托斯特尼筛在 范围内筛出素数
int limit = (int)floor(sqrt((long double)b));
for(int i = 2; i <= limit; i++){
if(isPrime) {
// 标记 i*i, i*i + i, ... 都不是素数
// 用 long long 避免 i*i 溢出
for(long long j = 1LL * i * i; j <= b; j += i){
isPrime = 0;
}
}
}
// 2) 在区间 内，若 isPrime = 1，则 x 是素数
// 再判断 x 是否回文，如果是就输出
for(int x = a; x <= b; x++){
if(isPrime){
// 检查回文
string s = to_string(x);
string r = s;
reverse(r.begin(), r.end());
if(s == r){
cout << s << "\n";
}
}
}
return 0;
}
线性筛
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll a,b;cin>>a>>b;
vector<bool> vis(b+1,0);
vector<ll> primes;
primes.reserve(b/10);
for(ll i=2;i<=b;i++){
if(vis==0)primes.push_back(i);
for(ll j=0;(long long)primes*i<=b&&j<primes.size();j++){
vis*i]=1;
if(i%primes==0){
break;
}
}
}
for(ll i=a;i<=b;i++){
if(vis==0){//注意别写错了，别写成vis==1了
string x=to_string(i);
string y=x;
reverse(y.begin(),y.end());
if(x==y){
cout<<x<<'\n';
}
}
}
return 0;
} 3.分解质因子 2
关键字：（质因数分解）
https://i-blog.csdnimg.cn/direct/c87f71d350ff48b487b056ddb8ae8b37.png
这题更爱MLE。。。。。。。。。什金。。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;cin>>t;///用long long会MLE
while(t--){
ll n;cin>>n;
ll t=n;
for(int i=2;(ll)i*i<=n;i++){///不把i*i强制转化为ll也会MLE
while(t%i==0){
t/=i;
cout<<i<<' ';
}
}
if(t!=1)cout<<t<<'\n';
else cout<<'\n';
}
return 0;
}
四，高精度加法，减法，乘法，除法
1.A+B Problem
https://i-blog.csdnimg.cn/direct/25901e95c14e443ca2f0ed9cf04785a8.png
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
string a,b;cin>>a>>b;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
vector<int> aa(a.length());
vector<int> bb(b.length());
for(ll i=0;i<a.length();i++)aa=a-'0';
for(ll i=0;i<b.length();i++)bb=b-'0';
vector<int> ans;
ll jinwei=0;
ll cur=0;
for(ll i=0;i<min(aa.size(),bb.size());i++){
cur=(aa+bb)+jinwei;
if(cur>=10)jinwei=1;
else jinwei=0;
//jinwei=(aa+bb)/10;
ans.push_back(cur%10);
}
if(aa.size()>bb.size()){
for(ll i=bb.size();i<aa.size();i++){
cur=aa+jinwei;
if(cur>=10)jinwei=1;
else jinwei=0;
ans.push_back(cur%10);
}
if(jinwei!=0)ans.push_back(jinwei);
}else if(aa.size()<bb.size()){
for(ll i=aa.size();i<bb.size();i++){
cur=bb+jinwei;
if(cur>=10)jinwei=1;
else jinwei=0;
ans.push_back(cur%10);
}
if(jinwei!=0)ans.push_back(jinwei);
}else{
if(jinwei!=0)ans.push_back(jinwei);
}
for(ll i=ans.size()-1;i>=0;i--)cout<<ans;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]