(桁和・約数列挙)ARC-060-D-桁和 / Digit Sum

問題URL→http://arc060.contest.atcoder.jp/tasks/arc060_b

まず、制約が10^11や10^12あたりだったらO(√n)あたり主に約数列挙・素因数分解などを注意しよう。

2<=b<=√nと√n#include <iostream> #include <vector> #include <string.h> #include <stack> #include <queue> #include <algorithm> #include <climits> #include <cmath> #include <map> #include <set> #include <assert.h> #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; //約数の列挙O(√n) vector<int> divisor(int n) { vector<int> res; for (int i=1; i*i<=n; i++) { if (n % i == 0) { res.push_back(i); if (i != n / i) res.push_back(n / i); } } return res; } int n, s; int f(int b, int n) { if (n < b) return n; else return f(b, n / b) + n % b; } signed main() { cin >> n >> s; if (s == n) { cout << n + 1 << endl; return 0; } for (int b=2; b*b<=n; b++) { if (f(b, n) == s) { cout << b << endl; return 0; } } vector<int> divs = divisor(n – s); set<int> ans; for (int div : divs) { int b = div + 1; if (f(b, n) == s) ans.insert(b); } if (ans.size() == 0) { cout << -1 << endl; } else { cout << *ans.begin() << 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;
}

大学数学を独学するのに役立つコンテンツ

AIロボットを作りたくてAIの勉強をするためにまずは大学の数学(微積、線形代数)を独学しています。

独学をしている中ですごくためになっているコンテンツを紹介します。

それが照井先生のYouTubeチャンネルです!

扱っている内容は微分積分、線形代数、計算機数学で、その大学での講義の録画が見れます。

このチャンネルを見つけるまで、参考書で独学していたのですが、

参考書以上の情報量のある講義が見れます。

大学数学を独学したい方におすすめです!