http://poj.org/problem?id=1845

主要是利用因子和公式。

这里给出三种方法,三份代码。

首先特判a%mod==1的情况,详见代码;注意到mod=9901是个质数,刚好前面的特判可以保证gcd(指数-1,9901)==1,所以可以直接求逆元。(用扩展欧几里得或者费马小定理均可)

如若题目所给的mod不是质数,该怎么做?更通用的解法是?
这时我们可以套用级数求和公式。

PS:代码用了long long,其实用int就行。

用逆元来解决:(扩展欧几里得法)

/*0ms,200KB*/

const ll mod = 9901;

vector<p2> factor;

void get_factor(ll n)
{
    ll sqrtn = sqrt(n + 0.5), i, tmpn = n, cnt;
    factor.clear();
    Forr(i, 2LL, sqrtn + 1)
    if (tmpn % i == 0LL)
    {
        for (tmpn /= i, cnt = 1LL; tmpn % i == 0LL; tmpn /= i) ++cnt;
        factor.PB(MP(i, cnt));
    }
    if (tmpn > 1LL) factor.PB(MP(tmpn, 1LL));
}

void exgcd(ll a, ll b, ll& x, ll& y)
{
    if (!b) x = 1LL, y = 0LL;
    else exgcd(b, a % b, y, x), y -= x * (a / b);
}

ll inv(ll a)
{
    ll x, y;
    exgcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}

ll Pow(ll a, ll r) ///a^r % mod
{
    ll ans = 1LL;
    for (; r; r >>= 1LL)
    {
        if (r & 1LL) ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}

int main()
{
    ll a, b, ans;
    int i;
    while (~SLL(a, b))
    {
        ans = 1LL;
        get_factor(a);
        For(i, factor.size())
        {
            if (factor[i].first % mod == 1LL) ans *= (factor[i].second * b + 1) % mod;
            else ans *= (Pow(factor[i].first % mod, factor[i].second * b + 1) - 1 + mod) % mod * inv(factor[i].first - 1) % mod;
            ans %= mod;
        }
        PL(ans);
    }
    return 0;
}

用逆元来解决:(费马小定理法)

/*16ms,204KB*/

const ll mod = 9901;

vector<p2> factor;

void get_factor(ll n)
{
    ll sqrtn = sqrt(n + 0.5), i, tmpn = n, cnt;
    factor.clear();
    Forr(i, 2LL, sqrtn + 1)
    if (tmpn % i == 0LL)
    {
        for (tmpn /= i, cnt = 1LL; tmpn % i == 0LL; tmpn /= i) ++cnt;
        factor.PB(MP(i, cnt));
    }
    if (tmpn > 1LL) factor.PB(MP(tmpn, 1LL));
}

ll Pow(ll a, ll r) ///a^r % mod
{
    ll ans = 1LL;
    for (; r; r >>= 1LL)
    {
        if (r & 1LL) ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}

int main()
{
    ll a, b, ans;
    int i;
    while (~SLL(a, b))
    {
        ans = 1LL;
        get_factor((int)a);
        For(i, factor.size())
        {
            if (factor[i].first % mod == 1LL) ans *= (factor[i].second * b + 1) % mod;
            else ans *= (Pow(factor[i].first % mod, factor[i].second * b + 1) - 1 + mod) % mod * Pow(factor[i].first - 1, mod - 2) % mod;
            ans %= mod;
        }
        PL(ans);
    }
    return 0;
}

套用级数求和公式,代码更短,更适用:

/*0ms,200KB*/

const ll mod = 9901;

vector<p2> factor;

void get_factor(ll n)
{
    ll sqrtn = sqrt(n + 0.5), i, tmpn = n, cnt;
    factor.clear();
    Forr(i, 2LL, sqrtn + 1)
    if (tmpn % i == 0LL)
    {
        for (tmpn /= i, cnt = 1LL; tmpn % i == 0LL; tmpn /= i) ++cnt;
        factor.PB(MP(i, cnt));
    }
    if (tmpn > 1LL) factor.PB(MP(tmpn, 1LL));
}

ll sumpow(ll a, ll r)
{
    ll ans = 1LL, tmp = 1LL;
    for (; r; r >>= 1LL)
    {
        if (r & 1LL) ans = (ans * a + tmp) % mod;
        tmp = tmp * (1LL + a) % mod;
        a = a * a % mod;
    }
    return ans;
}

int main()
{
    ll a, b, ans;
    int i;
    while (~SLL(a, b))
    {
        ans = 1LL;
        get_factor(a);
        For(i, factor.size()) ans = sumpow(factor[i].first % mod, factor[i].second * b) % mod * ans % mod;
        PL(ans);
    }
    return 0;
}

Comments

comments powered by Disqus