首页 > 代码库 > 2017-5-17-Train:喵哈哈村的魔法考试 Round #18 (Div.2)

2017-5-17-Train:喵哈哈村的魔法考试 Round #18 (Div.2)

A.喵哈哈村的古怪石碑(签到题)

描述

喵哈哈村有个奇怪的石碑,上面浮现出了一个奇怪的问题:

有一数列{an},给出其前三项a1,a2,a3,以及要求的项的编号n,并且数列{an}只可能是等差数列或者是首项为1的等比数列,要求A输出第n项模100007后的值。

输入

一行,四个整数,a1,a2,a3,n。满足:0< |a1|,|a2|,|a3|≤10^5,0<n<10^3。本题包含若干组测试数据。

输出

一行,一个数,即an模100007的值。(负数取模答案为负)

样例输入1

1 2 3 5

样例输出1

5

样例输入2

1 2 4 4

样例输出2

8

Solve:

直接按照等差等比通项公式算就可以了

Code:

技术分享
 1 #include <bits/stdc++.h> 2 static const int MOD=100007; 3 using namespace std; 4 typedef long long LL; 5 LL a1 , a2 , a3 , an , n; 6 void Dc() 7 { 8     LL d = a2 - a1; 9     an = a1 + (n - 1) * d;10     printf("%lld\n" , an % MOD);11 }12 LL QuickPower(LL a , LL b)13 {14     LL yaoyuan = 1;15     while(b)16     {17         if(b & 1)18             yaoyuan = (yaoyuan * a) % MOD;19         a = (a * a) % MOD;20         b >>= 1;21     }22     return yaoyuan;23 }24 void Db()25 {26     LL q = a2 / a1;27     an = a1 * QuickPower(q , n - 1);28     printf("%lld\n" , an % MOD);29 }30 int main()31 {32     while(~scanf("%lld%lld%lld%lld" , &a1 , &a2 , &a3 , &n))33     {34         if(a1 != 1 || (a1 == 1 && a2 - a1 == a3 - a2))35             Dc();36         else37             Db();38     }39 40 }
View Code

 

2017-5-17-Train:喵哈哈村的魔法考试 Round #18 (Div.2)