(フェルマーの小定理・逆元)ABC-024-D-動的計画法

問題URL→http://abc024.contest.atcoder.jp/tasks/abc024_d

なんか良く分からんがA,B,Cの値が余りであることを無視してA,B,Cの値からr,cを計算したら通った。

/*
#include <bits/stdc++.h>
//*/
//*
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
//*/
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007

#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

//(x^n)%modを求める
ll mod_pow(ll x, ll n, ll mod)
{
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

//aのmodにおける逆元を求める(フェルマーの小定理)
ll inverse(ll a, ll mod)
{
    return mod_pow(a, mod - 2, mod);
}

signed main()
{
    int A, B, C;

    cin >> A >> B >> C;
    int X = A * inverse(B, MOD) % MOD;
    int Y = A * inverse(C, MOD) % MOD;
    //cout << "X = " << X << " : Y = " << Y << endl;

    int c = (1 - X + MOD) * inverse(X + Y - 1, MOD) % MOD;
    int r = X * inverse(X + Y - 1, MOD) - 1;
    r %= MOD;
    //cout << "c = " << c << " : r = " << r << endl;

    cout << c << " " << r << endl;
}

(逆元・フェルマーの小定理)ARC-020-C-A mod B Problem(99点解法)

問題URL→http://arc020.contest.atcoder.jp/tasks/arc020_3

初めて逆元・フェルマーの小定理を自力で書いたかもしれない。
逆元はA/B mod pを求めるときにBで割る代わりにBの逆元B^-1を掛けるA*B^-1 mod pで余りが求められるというもの。
フェルマーの小定理はpが素数の場合、xの逆元はx^(p-2)であるというもの。

(自分用→詳しくはノート参照)

(コードID:9832)

#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;
const int INF = 1e9;

int N;
int a[10101], L[10101];
int B;

//(x^n)%modを求める
ll mod_pow(ll x, ll n, ll mod)
{
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

signed main()
{
    cin >> N;
    REP(i,N) {
        cin >> a[i] >> L[i];
    }
    cin >> B;

    if (B != MOD) return 0;

    int amari = 0;
    REP(i,N) {
        amari *= mod_pow(10, to_string(a[i]).length() * L[i], MOD);

        int bunsi = mod_pow(
                        mod_pow(10, to_string(a[i]).length(), MOD),
                        L[i],
                        MOD);
        bunsi -= 1;
        if (bunsi < 0) bunsi += MOD;

        int inv = mod_pow(10, to_string(a[i]).length(), MOD);
        inv -= 1;
        if (inv < 0) inv += MOD;
        inv = mod_pow(inv, MOD - 2, MOD);   //フェルマーの小定理

        int tempAmari = a[i] * bunsi;
        tempAmari %= MOD;
        tempAmari *= inv;
        tempAmari %= MOD;

        amari += tempAmari;
        amari %= MOD;
    }

    cout << amari << endl;
}