ZOJ 3903 Ant(公式推导)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这个公式推导过程是看的这位大牛的http://blog.csdn.net/bigbigship/article/details/49123643

扩展欧几里德求模的逆元方法：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + ;

ll exgcd(ll a, ll b, ll &x, ll &y)

{

    if (b == )

    {

        x = ;

        y = ;

        return a;

    }

    ll r = exgcd(b, a % b, x, y);

    ll t = x % mod;

    x = y % mod;

    y = ((t - a / b * y) % mod + mod) % mod;

    return r;

}

int main()

{

    ll x, y;

    ll inv2, inv4, inv6;

    exgcd(, mod, inv2, y);

    exgcd(, mod, inv4, y);

    exgcd(, mod, inv6, y);

    ll T, n;

    printf("%lld, %lld, %lld\n", inv2, inv4, inv6);

    scanf("%lld", &T);

    while (T--)

    {

        scanf("%lld", &n);

        n %= mod;

        ll ans = (n * n % mod + n) % mod * n % mod * n % mod * inv2 % mod;

        ans += ((n * (n + ) % mod) * n % mod * (n + ) % mod * inv2 % mod) % mod;

        ans += (n + ) * n % mod * (n + ) % mod * ( * n + ) % mod * inv6 % mod;

        ans =(((ans - n * n % mod * (n + ) % mod * (n + ) % mod * inv4 % mod + mod) % mod + mod) % mod);

        printf("%lld\n", ans);

    }

    return ;

}

费马小定理求模的逆元法

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + ;

ll power_mod(ll a, ll b, ll mod)

{

    ll ans = ;

    while (b)

    {

        if (b & ) ans = ans * a % mod;

        a = a * a % mod;

        b >>= ;

    }

    return ans;

}

int main()

{

    ll inv2 = power_mod(, mod - , mod);

    ll inv4 = power_mod(, mod - , mod);

    ll inv6 = power_mod(, mod - , mod);

    ll T, n;

    scanf("%lld", &T);

    while (T--)

    {

        scanf("%lld", &n);

        n %= mod;

        /*ll ans = (n * n % mod + n) % mod * n % mod * n % mod * inv2 % mod;

        ans += ((n * (n + 1) % mod) * n % mod * (n + 1) % mod * inv2 % mod) % mod;

        ans += (n + 2) * n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;

        ans =(((ans - n * n % mod * (n + 1) % mod * (n + 1) % mod * inv4 % mod + mod) % mod + mod) % mod);*/

        ll ans = n * (n + ) % mod * n % mod * n % mod * inv2 % mod;

        ans = (ans + n * (n + ) % mod * n % mod * (n + ) % mod * inv2 % mod) % mod;

        ans = (ans + n * (n + ) % mod * (n + ) % mod * ( * n + ) % mod * inv6 % mod) % mod;

        ans = (ans - n * n % mod * (n + ) % mod * (n + ) % mod * inv4 % mod + mod) % mod;

        printf("%lld\n", ans);

    }

    return ;

}