企业官网建设流程全解析

免费ppypp网站,百度权重划分等级,网络平台怎么挣钱的,嘉兴型网站系统总部【题目链接】 ybt 1615#xff1a;【例 1】序列的第 k 个数 本题的a、b、ca、b、ca、b、c#xff0c;等差数列公差、等比数列的公比都为整数。 【题目考点】 1. 快速幂 相关知识见#xff1a;洛谷 P1226 【模板】快速幂 2. 等差数列 相邻两项的差相等的数列为等差数列…【题目链接】ybt 1615【例 1】序列的第 k 个数本题的a 、 b 、 c a、b、ca、b、c等差数列公差、等比数列的公比都为整数。【题目考点】1. 快速幂相关知识见洛谷 P1226 【模板】快速幂2. 等差数列相邻两项的差相等的数列为等差数列。设第i ii项为a i a_iai​公差为d dd等差数列的递推公式a i a i − 1 d a_i a_{i-1}dai​ai−1​d等差数列的通项公式a i a 1 ( i − 1 ) d a_i a_1(i-1)dai​a1​(i−1)d3. 等比数列相邻两项的比值相等的数列为等比数列。设第i ii项为a i a_iai​公比为q qq等比数列的递推公式a i a i − 1 q a_i a_{i-1}qai​ai−1​q等比数列的通项公式a i a 1 q i − 1 a_i a_1q^{i-1}ai​a1​qi−1【解题思路】设M 200907 M200907M200907每组数据输入了数列的前三项先判断第二项减第一项的值与第三项减第二项的值是否相等即是否有b − a c − b b-ac-bb−ac−b如果满足该情况则该数列相邻两项的差相等是等差数列。否则就是等比数列。如果该数列是等差数列则公差为b − a b-ab−a使用通项公式求等差数列第k kk项再对M MM取模a k m o d M ( a 1 ( k − 1 ) d ) m o d M ( a ( k − 1 ) ( b − a ) ) m o d M a_k\bmod M(a_1(k-1)d)\bmod M(a(k-1)(b-a))\bmod Mak​modM(a1​(k−1)d)modM(a(k−1)(b−a))modM如果该数列是等比数列则公比为b a \frac{b}{a}ab​使用通项公式求等比数列第k kk项再对M MM取模a k m o d M a 1 q k − 1 m o d M a ( b a ) k − 1 m o d M ( a m o d M ) ( ( b a ) k − 1 m o d M ) m o d M a_k\bmod Ma_1q^{k-1}\bmod Ma(\frac{b}{a})^{k-1}\bmod M(a\bmod M)((\frac{b}{a})^{k-1}\bmod M)\bmod Mak​modMa1​qk−1modMa(ab​)k−1modM(amodM)((ab​)k−1modM)modM求( b a ) k − 1 m o d M (\frac{b}{a})^{k-1}\bmod M(ab​)k−1modM需要用到快速幂取模算法。本题无法使用递推公式求等差或等比数列第k kk项因为k kk最大会达到1 0 9 10^9109而递推求等差或等比数列第k kk项的时间复杂度是O ( n ) O(n)O(n)的写代码运行会超时【题解代码】解法1快速幂#includebits/stdc.husingnamespacestd;typedeflonglongLL;constintM200907;LLfastPow(LL a,LL b,LL m){LL r1;while(b0){if(b%21)rr*a%m;aa*a%m;b/2;}returnr;}intmain(){LL t,a,b,c,k;cint;while(t--){cinabck;if(c-bb-a)cout(a(k-1)*(b-a))%Mendl;else//c/b b/acouta*fastPow(b/a,k-1,M)%Mendl;}return0;}