求两个数的公约数有多少个

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;
}
int main(){int T,a,b;cin>>T;while(T--){int ans=1;cin>>a>>b;int g=gcd(a,b);if(g==1){cout<<"1"<<endl;continue;}ans++;for(int i=2;i*i<=g;i++){if(g%i==0)ans++;if(g%i==0&&g!=i*i)ans++;}cout<<ans<<endl;}
}

---

异或hard

#include<bits/stdc++.h>
#define hash h
#define int long long
using namespace std;
int T,x,ansa,ansb=2e9+10;
int hash[31];
signed main(){hash[0]=1;for(int i=1;i<=30;i++)hash[i]=hash[i-1]*2;cin>>T;while(T--){cin>>x;int a=1,b=1;for(int i=1;i<=30;i++){if(x==hash[i]){b=x+1;a=x^b;break;}if(x<hash[i]){b=hash[i-1];a=x^b;break;}}if(x==1)a=2,b=3;if(x==0)a=1,b=1;cout<<a<<" "<<b<<endl;
}} 

---

红蓝球的拿法dp

#include<bits/stdc++.h>using namespace std;
const int mod=1e9+7;
const int N = 1000001;
string s;
int n;
int T;
int dp[N][5][5];
int ans;int main(){cin>>T;while(T--){ans=0;cin>>n;cin>>s;//红色是0，蓝色是1dp[0][0][0]=1;for(int i=1;i<n;i++){for(int j=0;j<=4;j++){for(int k=0;k<=4;k++){if(s[i]=='R'){if(j>=1&&i>=2)dp[i][j][k]=(dp[i][j][k] + dp[i-2][j-1][k])%mod;//拿这个红球dp[i][j][k]=(dp[i][j][k] + dp[i-1][j][k])%mod;//不拿这个红球}if(s[i]=='B'){if(k>=1&&j>=1&&i>=2)dp[i][j][k]=(dp[i][j][k] + dp[i-2][j-1][k-1])%mod;//拿这个蓝球dp[i][j][k]=(dp[i][j][k] + dp[i-1][j][k])%mod;//不拿这个蓝球}}}}for(int k=1;k<=3;k++)ans=(ans+dp[n-1][4][k])%mod;cout<<ans<<endl;}
}

---

C. hard query problem
Problem description
scnucjh 遇到一个问题，由于他太菜，所以他向 Z3L5M 请教。
这个问题是这样的：
函数是 f(x) 表示 x 各个数位的和，例如，f(1) = 1,f(10) = 1, f(19) = 10, f(222) = 6。
现在给定一个长度为 n 的数组，每个数的值分别为 a1, a2, …, an. 现在给出 m 个操作，一
共有两种不同的操作：
• 1 操作：给定 L，R，将闭区间 [L, R] 里面的每个数作用 f(x)
• 2 操作：给定 L，R，求闭区间 [L, R] 里面的数的最小值
由于 Z3L5M 忙着写论文，所以现在这个问题交到你手上了。
Input
输入的第一行有两个整数 n，m。(1 ≤ n, m ≤ 100000) 第二行有 n 个整数，分别表示
a1, a2, …, an。(1 ≤ ai ≤ 1018) 接下来 m 行，每行三个整数 o，L，R (1 ≤ o ≤ 2, 1 ≤ L ≤ R ≤ n),
分别表示操作的类型，还有操作区间 L，R
Output
对于每个 2 操作，输出一行表示 [L, R] 内的最小值。
Sample Input
input
5 9
6666666666666666 6666666666666666 233333333333 23333333 2333
2 1 2
2 1 3
2 1 5
1 3 3
2 1 5
1 1 5
2 1 5
1 1 1
2 1 2
1Sample Output
output
6666666666666666
233333333333
2333
35
8
15
Hint
第 4 个操作之后数组变成 [6666666666666666 6666666666666666 35 23333333 2333].
第 6 个操作之后数组变成 [96 96 8 23 11].
第 8 个操作之后数组变成 [15 96 8 23 11]

---

区间修改，区间查询
要用到懒标记lazy-tag
首先，我们发现对于10的18次方减一这个数，最多进行三次f【x】之后就变成个位数了，也就是不再变了
具体代码如下

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100001;
const int M=1e18+10;
int n,m,w[N],ans;
int f(int x){if(x<10)return 0;int ans=0;while(x){ans+=x%10;x/=10;}return ans;
}
signed main(){int x=1e18;x--;int cnt=0;while(x){cout<<x<<endl;x=f(x);cnt++;}cout<<cnt<<endl;
}

所以modify的时候只需要对某个点modify三次就好了，如果要操作的这个区间里面，所有的数都变成个位数了，那么lazy=1，不再修改
思路清理完毕，准备开干！！

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+7;
int n,m,w[N],a,b,c;
struct node{int l,r,lazy,mi;
}tr[N*4];int f(int x){int res=0;while(x){res+=x%10;x/=10;}return res;
}void pushup(int u){tr[u].lazy=tr[u<<1].lazy&tr[u<<1|1].lazy;tr[u].mi=min(tr[u<<1].mi,tr[u<<1|1].mi);
}
void build(int u,int l,int r){if(l==r)tr[u]={l,r,0,w[l]};else{tr[u]={l,r,0};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}
void modify(int u,int l,int r){if(tr[u].lazy==1)return;if(tr[u].l==tr[u].r){tr[u].mi=f(tr[u].mi);if(tr[u].mi<10)tr[u].lazy=1;}else{int mid=tr[u].l+tr[u].r>>1;if(mid>=l)modify(u<<1,l,r);if(mid<r)modify(u<<1|1,l,r);pushup(u);}
}
int query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r)return tr[u].mi;int mid=tr[u].l+tr[u].r>>1;int ans=0x3f3f3f3f;//这里0x3f3f3f3f会wa掉，得要是1e18才acif(mid>=l)ans=min(ans,query(u<<1,l,r));if(mid<r)ans=min(ans,query(u<<1|1,l,r));return ans;
}
signed main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>w[i];build(1,1,n);while(m--){cin>>a>>b>>c;if(a==1)modify(1,b,c);if(a==2)cout<<query(1,b,c)<<endl;}
}

---

E. 梅森素数问题
Problem description
梅森数是形如 2
p − 1 的一类数，其中指数 p 是素数。如果梅森数是素数，就称为梅森素
数。
能用 c++ int 类型表示的梅森素数一共有如下 7 个: 3, 7, 127, 8191, 131071, 524287,
2147483647。给你一个整数 x, 你需要找到最小的，且大于或等于 x 的梅森素数。
Input
第一行一个数 T，表示测试的组数。(1 ≤ T ≤ 2000)
每组一个整数 x(0 ≤ x ≤ 1000000000)，含义如题意所示
Output
对于每组测试，输出一行，表示大于或等于 x 的最小的梅森素数。
Sample Input&Output
input 1 output 1
10 3
1 3
2 3
3 7
4 7
5 7
6 7
7 127
8 127
9 127
10

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,x;
const int N = 1e9;
int f[10000],ha[7];signed main(){//3, 7, 127, 8191, 131071, 524287,2147483647ha[0]=3;ha[1]=7;ha[2]=127;ha[3]=8191;ha[4]=131071;ha[5]=524287;ha[6]=2147483647;cin>>n;while(n--){cin>>x;if(x<3){puts("3");continue;}for(int i=0;i<7;i++){if(x<=ha[i]){cout<<ha[i]<<endl;break;}}}
}

---

F. Yet Another Race to 1 Problem
Problem description
给定一个数 x，你每次可以做如下 3 种操作：
• 如果存在一个整数 d(1 < d < x)，使得 d 整除 x，把 x 变成 d。
• 把 x 减 1
• 把 x 减 2
请问，最少多少步可以把 x 变成 1。
Input
第一行一个数 T，表示测试的组数。(1 ≤ T ≤ 2000)
每组一个正整数 x(0 < x ≤ 1000000000)，含义如题意所示
Output
对于每组测试，输出一行，表示 x 最少要经过多少步上述操作得到 1。
Sample Input&Output
input 1 output 1
3 2
12 1
2 0
1

---

K. 喜欢做题的 lre
Problem description
SCNU 展开了一次集训，一共 n 天，lre 也参加了这场集训，lre 喜欢 3 个 OJ，所以只
会在这三个 OJ 上面做题，这三个 OJ 是 ZOJ，POJ，CF。
lre 每天 AC 恰好一道题目，每 AC 一道题目，他都能得到一些快乐值。对于第 i 天
(1 ≤ i ≤ n)，lre 可以选择一个 OJ，并且 AC 里面的一道题目。
• 选择 ZOJ，他将得到 Zi 的快乐值
• 选择 POJ，他将得到 Pi 的快乐值。
• 选择 CF，他将得到 Ci 的快乐值。
但是，lre 绝对不会连续两天在同一个 OJ 做题，他觉得这样太枯燥了。请问，第 n 天结
束后，lre 最多能获得多少快乐值？
Input
第一行有一个数 T(1 ≤ T ≤ 100000)
每组第一行包含一个数 n，表示集训有 n 天。 1 ≤ n ≤ 1000000)
接下来有 n 行，每行有三个数 Zi，Pi ，Ci。(1 ≤ Zi
, Pi
, Ci ≤ 100)
数据保证各组的 n 之和不会超过 1000000。
Output
对于每组测试，输出一行，表示答案。
Sample Input&Output
input 1 output 1
2 21
3 5
1 4 7
5 2 8
3 6 9
1
5 2 2

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e7+7;
const int M=1e5+10;
int T,n,w0[M],w1[M],w2[M];
int dp[N][3];
signed main(){cin>>T;while(T--){//memset(dp,0,sizeof dp);cin>>n;for(int i=1;i<=n;i++)cin>>w0[i]>>w1[i]>>w2[i];for(int i=1;i<=n;i++){dp[i][0]=max(dp[i-1][1],dp[i-1][2])+w0[i];dp[i][1]=max(dp[i-1][0],dp[i-1][2])+w1[i];dp[i][2]=max(dp[i-1][0],dp[i-1][1])+w2[i];}cout<<max(max(dp[n][0],dp[n][1]),dp[n][2])<<endl;}
}

---

G. hard graph problem
Problem description
给定一个 n 个点 m 条边的带权无向图, n 个点编号从 1 到 n，再给定两个点 s 和 t，可
能有重边或者自环。整个图也可能不连通，但保证 s 和 t 是连通的。你需要回答两个问题：
• 问题 1：从 s 到 t 的最短路的长度
• 问题 2：从 s 到 t 的最短路最少要经过多少个节点 (包括 s 和 t)
Input
第一行四个由空格隔开的整数 n、m、s、t。(2 ≤ n ≤ 2500, 1 ≤ m ≤ 6200, 1 ≤ s, t ≤ n 且
s ̸= t)
之后的 m 行，每行三个正整数 ai 、bi、wi，表示一条从 ai 到 bi 长度为 wi 的边。
(1 ≤ ai, bi ≤ n 且 1 ≤ wi ≤ 10000)
Output
输出包含两行，第一行表示问题 1 的答案，第二行表示问题 2 的答案。
Sample Input&Output
input 1 output 1
7 11 5 4 7
2 4 2 4
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

#include <iostream>
#include <cstring>
#include <algorithm>
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 25001,M=70001;
int dist[N];
bool vis[N];
int st[N];
int a,b,c,n,m,s,t;
int h[N],ne[M],e[M],w[M],idx;
int pre[N];
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa(int start,int end){memset(dist,0x3f,sizeof dist);dist[start]=0;vis[start]=1;queue<int>Q;Q.push(start);while(!Q.empty()){int now=Q.front();Q.pop();vis[now]=0;for(int i=h[now];~i;i=ne[i]){int j=e[i];if(dist[j]>dist[now]+w[i]){dist[j]=dist[now]+w[i];//直接从起点走到j太远了，我从now走过来pre[j]=now;//j从now走过来if(!vis[j]){vis[j]=1;Q.push(j);}}}}
}void findpath(int start,int end){pre[start]=0;stack<int>path;//path.push(end);int cnt=0;for(int i=end;i!=0;i=pre[i]){if(!st[i])st[i]=1 , path.push(i);else break;}cout<<path.size();// while(path.size()){//     cout<<path.top()<<endl;//     path.pop();// }
}signed main(){cin>>n>>m>>s>>t;memset(h,-1,sizeof h);while(m--){cin>>a>>b>>c;if(a==b)continue;add(a,b,c);add(b,a,c);}spfa(s,t);cout<<dist[t]<<endl;findpath(s,t);
}

---

A. 奇妙数字问题
Problem description
有了 0 到 9 这 10 个阿拉伯数字，我们可以构造出任意的自然数。
但是，在奇异世界里面，有一些阿拉伯数字丢失了，我们用一个长度为 10 的 01 串 s 来
表示奇异世界里面拥有那些阿拉伯数字。01 串 s 下标从 0 开始编号，上面的一位为 1，表示
奇异世界拥有该下标的对应的阿拉伯数字。例如：
•“1000010001”，表示奇异世界有数字 0，5，9
•“1111000100”，表示奇异世界有数字 0，1，2，3，7
而你最喜欢的数字是 x，你希望用奇异世界中的数字组成一个 x 的倍数 y，即 y 除以 x 的余
数是 0，如果在闭区间 [1, 10100] 里面能够找到，输出最小的 x 的倍数，否则，输出-1。
Input
第一行一个数 T，表示测试的组数。(1 ≤ T ≤ 200) 每组有一长度为 10 的 01 串和一个
正整数 x(0 < x ≤ 3000)，含义如题意所示
Output
对于每组测试，输出一行，表示答案，有解时，解不能含前导 0。
Sample Input
input
10
0000001000 98
1111111101 88
1000000001 89
0000001000 232
1111000000 1230
0111111000 777
0111100000 666
1000010000 3000
1000011111 29
1100000000 33
1Sample Output
output
666666666666666666666666666666666666666666
176
99090909
-1
1230
1554
1332
555000
58
11111

#include <iostream>
#include <cstring>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[10];
int vis[3000];
struct node{int sum;string s;
};
signed main(){int T;cin>>T;while(T--){memset(vis,0,sizeof vis);string s;int x;cin>>s>>x;queue<node>Q;for(int i=0;i<=9;i++){if(s[i]=='0'){a[i]=0;continue;}a[i]=1;string w="";w+=(i+'0');if(i!=0)Q.push({i,w});}int flag=0;while(!Q.empty()){auto t=Q.front();Q.pop();if(t.s.length()>=100)continue;if(t.sum%x==0){flag=1;cout<<t.s<<endl;break;}for(int i=0;i<=9;i++){if(a[i]==0)continue;int now_sum=(t.sum*10+i)%x;if(vis[now_sum])continue;//这里是剪纸，也就是说如果对这个数我们又回到了原点//说明在绕圈，那么就continue，而不是break掉//continue的意思是说这条路已经走过了，是行不通的，不要再走一次vis[now_sum]=1;string now_s="";now_s+=(i+'0');now_s=t.s+now_s;Q.push({now_sum,now_s});}}if(!flag)puts("-1");}
}

---

H. pjy 与数字 (2)
Problem description
pjy 已经被 ACM 打趴在地上，再也不想看到 2,3,5 这三个数字了。
捣蛋鬼 cjh 故意在纸上写长度为 n 的序列 A，它们只包含 2,3,5。同时，cjh 每写完一个
数，lre 记录该数字出现的次数, 得到序列 B。例如：
• 如果 cjh 写 A=[2, 2, 3, 2, 5, 5, 5]，那么 lre 会依次写 B=[ 1, 2, 1, 3, 1, 2, 3]
• 如果 cjh 写 A=[3, 3, 3, 3, 3]，那么 lre 会依次写 B=[ 1, 2, 3, 4, 5]
做完这个过程之后，cjh 把他写的序列扔掉，只保留 lre 写的序列，然后跑去问 pjy，” 请找
到一个只包含 2,3,5 的序列，且按照 lre 记录的规则，能得到 B 序列。”。
pjy 真的不想再看到 2,3,5 这三个数字了，所以现在请你帮忙。
Input
第一行表示一个数 n(1 ≤ n ≤ 1000000) 第二行 n 个数，用空格隔开，表示 lre 写的序列
B。我们的输入保证有解。
Output
输出仅一行，一个字符串，没有空格隔开，表示 cjh 写的序列 A。如果有多种可能，请
输出字典序最小的解。
Sample Input&Output
input 1 output 1
7 2232533
1 2 1 3 1 2 3

#include<bits/stdc++.h>
using namespace std;
int n,sum2,sum3,sum5;
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;int x;for(int i=1;i<=n;i++){cin>>x;if(sum2==x-1){sum2++;cout<<"2";}else if(sum3==x-1){sum3++;cout<<"3";}else{sum5++;cout<<"5";}}
}

---

I. pjy 与数字 (3)
Problem description
pjy 已经被 ACM 打趴在地上，再也不想看到 2,3,5 这三个数字了。
捣蛋鬼 cjh 故意在纸上写长度为 n 的序列 A，它们只包含 2,3,5。同时，cjh 每写完一个
数，lre 记录该数字出现的次数, 得到序列 B。例如：
• 如果 cjh 写 A=[2, 2, 3, 2, 5, 5, 5]，那么 lre 会依次写 B=[ 1, 2, 1, 3, 1, 2, 3]
• 如果 cjh 写 A=[3, 3, 3, 3, 3]，那么 lre 会依次写 B=[ 1, 2, 3, 4, 5]
做完这个过程之后，cjh 把他写的序列扔掉，只保留 lre 写的序列，然后跑去问 pjy，“请问有
多少个长度为 n 的只包含 2, 3, 5 的序列，且按照 lre 记录的规则，能得到 B 序列?”。
两个序列相等，指的是他们的每个元素都相等。
pjy 真的不想再看到 2,3,5 这三个数字了，所以现在请你帮忙。
Input
第一行表示一个数 n(1 ≤ n ≤ 1000000) 第二行 n 个数，用空格隔开，表示 lre 写的序列
B。
Output
仅一行，表示答案，即 A 序列有多少种可能。(由于答案有可能很大，你只需要输出答案
除以 1000000007 取余数的结果。)
Sample Input&Output
input 1 output 1
3 12
1 1 2
input 2 output 2
3 0
2 1 1

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,sum2,sum3,sum5;
int ans;
int x;int main(){cin>>n;long long ans=1;for(int i=1;i<=n;i++){cin>>x;int cnt=0;if(sum2==x-1)cnt++;if(sum3==x-1)cnt++;if(sum5==x-1)cnt++;if(sum2==x-1)sum2++;else if(sum3==x-1)sum3++;else if(sum5==x-1)sum5++;ans=(ans*cnt)%mod;if(ans==0){cout<<"0";return 0;}}cout<<ans;}

---