UOJ Logo NaCl的博客

博客

只用等比数列求和过掉 #115

2020-12-20 00:32:56 By NaCl

分治题解见此处

显然,若 $a\mod b=c$,则 $ah\mod bh=ch$。

因此先以 $(a-1)m$ 为模数作快速幂,再除以 $(a-1)$ 即可。

#include <stdio.h>
#include <stdlib.h>

int power_mod(int base, long long int exp, int mod)
{
    long long int result = 1, b2 = base;
    while (exp) {
        if (1 & exp) result = result * b2 % mod;
        b2 = b2 * b2 % mod;
        exp >>= 1;
    }
    return (int)result;
}

int main()
{
    int a, m, m1;
    long long int k;
    scanf("%d%lld%d", &a, &k, &m);
    m1 = m * (a - 1);
    printf("%d\n",
        (m - 1 + (m1 - 1 + power_mod(a, 1 + k, m1)) % m1 / (a - 1)) % m);
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。