AtCoder Beginner Contest 293 - E - Geometric Progression

Solost

2023 年 03 月 16 日

222 次浏览

暂无评论

1493字数

题目题解

![image(2).png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F16%2Fimage%282%29.png)

## 题目链接

[题目链接](https://atcoder.jp/contests/abc293/tasks/abc293_e)

## sloution

![image(3).png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F16%2Fimage%283%29.png)

补充一点点，为什么奇数不能用最后一个公式呢？因为提出A的时候，结果是`f(p/2)*xxxx`这个需要提出一个式子，所以奇数的时候不能二分，需要用第二个式子来把他再转化成偶数。

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
ll a, x, m;
ll f[N];

ll qmi(ll n, ll k, ll p)
{
    ll res = 1 % p;
    while (k) {
        if (k & 1)
            res = res * n % p;
        n = n * n % p;
        k >>= 1;
    }
    return res;
}

ll sum(ll p)
{
    if (p == 0)
        return 1 % m;
    if (p % 2) {
        return (sum(p / 2) % m * (qmi(a, p / 2 + 1, m) + 1) % m) % m;
    } else {
        return (a * sum(p - 1) % m + 1) % m;
    }
}

void solve()
{
    cin >> a >> x >> m;
    ll ans = sum(x - 1);
    cout << ans << endl;
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 03 月 16 日