Codeforces 963 A. Alternating Sum(快速幂，逆元)

[Codeforces 963 A. Alternating Sum](http://codeforces.com/problemset/problem/963/A)
题目大意：给出一组长度为n+1且元素为1或者-1的数组S（0~n），数组每k个元素为一周期，保证n+1可以被k整除。给a和b，求![](https://images2018.cnblogs.com/blog/1330878/201805/1330878-20180526212011017-1327546933.png)对1e9+9取模的结果
思路：容易想到，每个周期的∑组成的数列成等比，公比q=（b/a)^k，因此可以用等比数列公式求和。为了保证时间复杂度，需要用到快速幂运算；为了防止中间过程值溢出，需要多处取模，其中用费马小定理求逆元；
代码：
```C++
#include
#include
#include
using namespace std;
typedef long long ll;
const int mod=1e9+9;
ll qpow(ll x,ll n,ll m)
{
ll res=1;
while (n>0)
{
if (n&1)
res=res*x%m;
n>>=1;
x=x*x%m;
}
return res;
}
ll inv(ll x,ll m)
{
return qpow(x,m-2,m);
}
int main()
{
int n,a,b,k,i;
cin>>n>>a>>b>>k;
cin.get();
ll ft=0,q,ans;
for (i=0;i

巴特西

Codeforces 963 A. Alternating Sum(快速幂，逆元)

最新文章

热门文章