当前位置：首页 > news >正文

C++倍增法（练习题）

news 2026/6/12 13:06:48

【倍增查找】

请在一个有序递增数组中（不存在相同元素），找出第一个>=x的值的位置，如果x在数组中不存在，请输出-1。
【输入】
第一行，一个整数n，代表数组元素个数（n <= 100）
第二行，n个整数，代表数组的n个递增元素（1<=数组元素值<=10^8）
第三行，一个整数x，代表要查找的数（0<=x<=10^8）
【输出】
x在数组中的位置，位置从1开始编号；没找到，输出-1。
【输入用例】
10
1 3 5 7 9 11 13 15 17 19
3
【输出用例】
2

#include<iostream>usingnamespacestd;inta[110];intn;// 在数组a[1~n]中倍增查找x的位置// 如果找到x，则返回x在数组a中的下标，否则返回-1intsearch(intx){intL=1,p=1;while(p){//如果还能扩增范围(l)就继续if(L+p<=n&&a[L+p]<=x){L+=p;//增加已知范围p<<=1;//成倍增长，相当于p*=2}else{p>>=1;//缩小范围}}returna[L]>=x?L:-1;}intmain(){intx;// 要查找的值cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}cin>>x;cout<<search(x);return0;}/* 【输入用例2】 10 1 3 5 7 9 11 13 15 17 19 20 【输出用例2】 -1 【输入用例3】 10 1 3 5 7 9 11 13 15 17 19 -1 【输出用例3】 1 【输入用例4】 5 1 3 5 7 9 5 【输出用例4】 3 【输入用例5】 4 2 4 6 8 2 【输出用例5】 1 【输入用例6】 6 1 2 3 4 5 10 10 【输出用例6】 6 */

斐波那契数列（倍增法）

【描述】关于斐波那契数列张三已经了解到不少知识，他发现除了其他方法能够实现精准输出斐波那契数列第几项外，利用倍增法似乎也能完成。请你帮助他设计一个倍增法输出斐波那契数列的程序。
【输入描述】输入一个数，表示需要输出第几项斐波那契数的值。
【输出描述】输出该项的斐波那契数值
【样例输入】
9
【样例输出】
F(9) = 34

#include<iostream>usingnamespacestd;// 快速倍增法计算斐波那契数// 返回一个数对：{ F(n), F(n+1) }// 使用 long long 以支持较大的数值pair<longlong,longlong>fib_pair(intn){if(n==0){// F(0) = 0, F(1) = 1return{0,1};}// 递归计算 n/2 的结果autop=fib_pair(n>>1);// p = { F(k), F(k+1) } where k = n/2longlonga=p.first;// a = F(k)longlongb=p.second;// b = F(k+1)// 计算 F(2k) = F(k) * [2*F(k+1) - F(k)]longlongc=a*(2*b-a);// 计算 F(2k+1) = F(k)^2 + F(k+1)^2longlongd=a*a+b*b;// 根据 n 的奇偶性返回结果if(n&1){// 如果 n 是奇数: n = 2k + 1// 返回 { F(2k+1), F(2k+2) }// F(2k+2) = F(2k+1) + F(2k)return{d,c+d};}else{// 如果 n 是偶数: n = 2k// 返回 { F(2k), F(2k+1) }return{c,d};}}// 包装函数：给定 n，返回 F(n)longlongfibonacci(intn){returnfib_pair(n).first;}intmain(){intn;cin>>n;cout<<"F("<<n<<") = "<<fibonacci(n)<<endl;return0;}/* 【输入用例2】 0 【输出用例2】 F(0) = 0 【输入用例3】 15 【输出用例3】 F(15) = 610 【输入用例4】 25 【输出用例4】 F(25) = 75025 【输入用例5】 40 【输出用例5】 F(40) = 102334155 */

模逆元

【描述】模逆元是模运算中的乘法逆元素，对于整数 a 和模数 m，若存在整数 b 满足：a * b≡ 1 mod m，则称 b 为 a 在模 m 下的逆元，记作 a^-1
模逆元存在条件：a 与 m 必须互质（即 gcd(a,m)=1）。现要求你编写程序使用快速幂算法计算模逆元。
【输入描述】输入为两个正整数，底数a和模数m
【输出描述】输出为底数a在模数m下的逆元
【样例输入1】2 3
【样例输出1】2 在模 3 下的逆元是: 2
【样例输入2】2 4
【样例输出2】逆元不存在（可能原因：a和m不互质或m非质数）

#include<iostream>usingnamespacestd;// 快速幂算法计算 (base^exp) % modlonglongfastPow(longlongbase,longlongexp,longlongmod){longlongresult=1;base%=mod;// 防止base过大while(exp>0){if(exp&1){// 如果当前二进制位为1result=(result*base)%mod;}base=(base*base)%mod;// 底数平方exp>>=1;// 指数右移一位}returnresult;}intmain(){longlonga,m;cin>>a>>m;//输入底数a和模数m（用空格分隔）// 检查模数是否为质数（此处假设m是质数）// 实际应用中需要添加质数判断逻辑// 计算模逆元 a^(m-2) mod mlonglonginverse=fastPow(a,m-2,m);// 验证结果是否有效if(inverse*a%m==1){cout<<a<<" 在模 "<<m<<" 下的逆元是: "<<inverse<<endl;}else{cout<<"逆元不存在（可能原因：a和m不互质或m非质数）"<<endl;}return0;}/* 【输入用例2】 3 7 【输出用例2】 3 在模 7 下的逆元是: 5 【输入用例3】 123456 1000003 【输出用例3】 123456 在模 1000003 下的逆元是: 414894 【输入用例4】 3 8 【输出用例4】 逆元不存在（可能原因：a和m不互质或m非质数） 【输入用例5】 4 2 【输出用例5】 逆元不存在（可能原因：a和m不互质或m非质数） 【输入用例6】 2 9 【输出用例6】 逆元不存在（可能原因：a和m不互质或m非质数） */

静态区间最大值查询

【描述】使用ST算法求解数组区间内的最大值为多少
【输入描述】首先一行输入一个数字n，接着第二行输入n个数组元素，第三行输入需要查询的区间数q，接下来的q行输入q个区间。
【输出描述】输出不同的区间中最大值
【样例输入】
5
3 3 3 3 3
3
1 5
2 4
3 3
【样例输出】
区间[1,5]的最大值为: 3
区间[2,4]的最大值为: 3
区间[3,3]的最大值为: 3

#include<iostream>usingnamespacestd;constintMAX_N=1010;intst[MAX_N][20];// st[i][j]表示从i开始长度为2^j的区间最大值intarr[MAX_N];// 构建ST表voidbuildST(intn){// 初始化长度为1的区间for(inti=1;i<=n;i++){st[i][0]=arr[i];}// 计算长度大于1的区间for(intj=1;(1<<j)<=n;j++){for(inti=1;i+(1<<j)-1<=n;i++){st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);}}}// 查询区间[l,r]的最大值intqueryRMQ(intl,intr){intlen=r-l+1;intk=0;while((1<<(k+1))<=len)k++;// 查询区间[l, l+2^k-1]和[r-2^k+1, r]的最大值returnmax(st[l][k],st[r-(1<<k)+1][k]);}intmain(){intn,q;cin>>n;//输入数组大小n//输入数组元素for(inti=1;i<=n;i++){cin>>arr[i];}buildST(n);//输入查询次数qcin>>q;while(q--){intl,r;cin>>l>>r;cout<<"区间["<<l<<","<<r<<"]的最大值为: "<<queryRMQ(l,r)<<endl;}return0;}/* 【输入用例2】 1 5 1 1 1 【输出用例2】 区间[1,1]的最大值为: 5 【输入用例3】 6 1 2 3 4 5 6 2 1 6 3 5 【输出用例3】 区间[1,6]的最大值为: 6 区间[3,5]的最大值为: 5 【输入用例4】 5 9 7 5 3 1 2 1 5 2 4 【输出用例4】 区间[1,5]的最大值为: 9 区间[2,4]的最大值为: 7 【输入用例5】 8 3 9 2 7 5 8 1 6 3 1 8 4 6 2 5 【输出用例5】 区间[1,8]的最大值为: 9 区间[4,6]的最大值为: 8 区间[2,5]的最大值为: 9 【输入用例6】 7 -3 0 15 -8 25 7 -1 3 1 7 3 6 5 5 【输出用例6】 区间[1,7]的最大值为: 25 区间[3,6]的最大值为: 25 区间[5,5]的最大值为: 25 */

区间GCD查询

【描述】使用ST表来预处理数组，快速查询任意区间的最大公约数（GCD）
【输入描述】首先一行输入一个数字n，接着第二行输入n个数组元素，第三行输入需要查询的区间数q，接下来的q行输入q个区间。
【输出描述】输出q个区间内所有元素的最大公约数
【样例输入】
6
2 4 5 7 11 13
2
1 2
3 4
【样例输出】
区间[1,2]的GCD为: 2
区间[3,4]的GCD为: 1

#include<iostream>usingnamespacestd;constintMAX_N=1010;intst[MAX_N][20];// st[i][j]表示从i开始长度为2^j的区间的GCD值intarr[MAX_N];// 计算两个数的最大公约数intgcd(inta,intb){while(b){inttemp=b;b=a%b;a=temp;}returna;}// 构建ST表voidbuildST(intn){// 初始化长度为1的区间for(inti=1;i<=n;i++){st[i][0]=arr[i];}// 计算长度大于1的区间for(intj=1;(1<<j)<=n;j++){for(inti=1;i+(1<<j)-1<=n;i++){st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);}}}// 查询区间[l,r]的最大公约数intqueryGCD(intl,intr){intlen=r-l+1;intk=0;while((1<<(k+1))<=len)k++;// 查询区间[l, l+2^k-1]和[r-2^k+1, r]的最大公约数returngcd(st[l][k],st[r-(1<<k)+1][k]);}intmain(){intn,q;//输入数组大小ncin>>n;//输入数组元素for(inti=1;i<=n;i++){cin>>arr[i];}buildST(n);//输入查询次数qcin>>q;while(q--){intl,r;cin>>l>>r;cout<<"区间["<<l<<","<<r<<"]的GCD为: "<<queryGCD(l,r)<<endl;}return0;}/* 【输入用例2】 1 5 1 1 1 【输出用例2】 区间[1,1]的GCD为: 5 【输入用例3】 5 0 0 0 0 0 3 1 5 2 3 5 5 【输出用例3】 区间[1,5]的GCD为: 0 区间[2,3]的GCD为: 0 区间[5,5]的GCD为: 0 【输入用例4】 7 0 6 0 9 0 12 0 3 1 7 2 5 4 6 【输出用例4】 区间[1,7]的GCD为: 3 区间[2,5]的GCD为: 3 区间[4,6]的GCD为: 3 【输入用例5】 4 123456 234567 345678 456789 2 1 4 2 3 【输出用例5】 区间[1,4]的GCD为: 3 区间[2,3]的GCD为: 3 【输入用例6】 8 4 8 12 16 20 24 28 32 3 1 8 2 6 5 7 【输出用例6】 区间[1,8]的GCD为: 4 区间[2,6]的GCD为: 4 区间[5,7]的GCD为: 4 */