#566190 (C++14) No.1261 数字集め

提出ソース

結果

問題	No.1261 数字集め
ユーザー	magsta
提出日時	2020-10-12 22:34:43
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,134 ms / 8,000 ms
コード長	3,425 bytes
コンパイル時間	970 ms
コンパイル使用メモリ	78,664 KB
実行使用メモリ	35,840 KB
最終ジャッジ日時	2024-07-21 03:40:58
合計ジャッジ時間	33,081 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,134 ms 35,672 KB
testcase_01	AC	114 ms 14,820 KB
testcase_02	AC	233 ms 26,752 KB
testcase_03	AC	233 ms 26,972 KB
testcase_04	AC	153 ms 18,688 KB
testcase_05	AC	309 ms 34,304 KB
testcase_06	AC	174 ms 20,864 KB
testcase_07	AC	249 ms 27,776 KB
testcase_08	AC	140 ms 17,024 KB
testcase_09	AC	182 ms 21,376 KB
testcase_10	AC	11 ms 5,376 KB
testcase_11	AC	314 ms 33,920 KB
testcase_12	AC	282 ms 30,848 KB
testcase_13	AC	249 ms 28,160 KB
testcase_14	AC	30 ms 6,272 KB
testcase_15	AC	126 ms 15,616 KB
testcase_16	AC	250 ms 27,904 KB
testcase_17	AC	202 ms 23,168 KB
testcase_18	AC	127 ms 15,872 KB
testcase_19	AC	239 ms 27,136 KB
testcase_20	AC	35 ms 6,784 KB
testcase_21	AC	326 ms 35,748 KB
testcase_22	AC	325 ms 35,712 KB
testcase_23	AC	324 ms 35,712 KB
testcase_24	AC	322 ms 35,712 KB
testcase_25	AC	322 ms 35,712 KB
testcase_26	AC	324 ms 35,584 KB
testcase_27	AC	326 ms 35,584 KB
testcase_28	AC	324 ms 35,584 KB
testcase_29	AC	335 ms 35,712 KB
testcase_30	AC	323 ms 35,712 KB
testcase_31	AC	328 ms 35,712 KB
testcase_32	AC	324 ms 35,712 KB
testcase_33	AC	324 ms 35,712 KB
testcase_34	AC	324 ms 35,840 KB
testcase_35	AC	323 ms 35,840 KB
testcase_36	AC	323 ms 35,712 KB
testcase_37	AC	323 ms 35,712 KB
testcase_38	AC	324 ms 35,712 KB
testcase_39	AC	324 ms 35,712 KB
testcase_40	AC	322 ms 35,712 KB
testcase_41	AC	322 ms 35,636 KB
testcase_42	AC	322 ms 35,712 KB
testcase_43	AC	324 ms 35,712 KB
testcase_44	AC	340 ms 32,000 KB
testcase_45	AC	128 ms 10,112 KB
testcase_46	AC	159 ms 19,072 KB
testcase_47	AC	166 ms 14,592 KB
testcase_48	AC	267 ms 27,392 KB
testcase_49	AC	302 ms 31,616 KB
testcase_50	AC	330 ms 28,800 KB
testcase_51	AC	87 ms 10,624 KB
testcase_52	AC	26 ms 5,376 KB
testcase_53	AC	118 ms 10,880 KB
testcase_54	AC	165 ms 11,904 KB
testcase_55	AC	71 ms 7,424 KB
testcase_56	AC	117 ms 8,704 KB
testcase_57	AC	265 ms 26,240 KB
testcase_58	AC	112 ms 10,240 KB
testcase_59	AC	372 ms 32,512 KB
testcase_60	AC	131 ms 11,520 KB
testcase_61	AC	150 ms 14,848 KB
testcase_62	AC	356 ms 29,568 KB
testcase_63	AC	57 ms 8,064 KB
testcase_64	AC	395 ms 34,560 KB
testcase_65	AC	235 ms 24,320 KB
testcase_66	AC	188 ms 20,864 KB
testcase_67	AC	270 ms 29,696 KB
testcase_68	AC	190 ms 19,840 KB
testcase_69	AC	170 ms 19,456 KB
testcase_70	AC	195 ms 16,128 KB
testcase_71	AC	314 ms 28,288 KB
testcase_72	AC	140 ms 12,672 KB
testcase_73	AC	152 ms 14,208 KB
testcase_74	AC	77 ms 8,704 KB
testcase_75	AC	221 ms 18,688 KB
testcase_76	AC	262 ms 26,112 KB
testcase_77	AC	298 ms 29,952 KB
testcase_78	AC	29 ms 5,376 KB
testcase_79	AC	298 ms 30,976 KB
testcase_80	AC	55 ms 5,376 KB
testcase_81	AC	68 ms 6,528 KB
testcase_82	AC	269 ms 24,960 KB
testcase_83	AC	171 ms 13,312 KB
testcase_84	AC	428 ms 35,840 KB
testcase_85	AC	427 ms 35,840 KB
testcase_86	AC	429 ms 35,840 KB
testcase_87	AC	430 ms 35,840 KB
testcase_88	AC	431 ms 35,840 KB
testcase_89	AC	425 ms 35,840 KB
testcase_90	AC	429 ms 35,840 KB
testcase_91	AC	427 ms 35,840 KB
testcase_92	AC	431 ms 35,840 KB
testcase_93	AC	430 ms 35,840 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define MOD 1000000007
using namespace std;

long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a) {
    return modpow(a, MOD - 2);
}

vector<long long> enum_divisors(long long N) {
    vector<long long> res;
    for (long long i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            res.push_back(i);
            // 重複しないならば i の相方である N/i も push
            if (N/i != i) res.push_back(N/i);
        }
    }
    // 小さい順に並び替える
    sort(res.begin(), res.end());
    return res;
}

long long p_q_r(long long p, long long q, long long r, long long M){
    if (r > p) swap(p, r);
    if (q > p) swap(p, q);
    if (r > q) swap(q, r);
    long long a, b, c, d, e;
    a = modpow(p, M - 2);
    b = modpow(q, M - 2);
    c = modpow(r, M - 2);
    d = (((a - c) * modinv(p - r) % MOD) + MOD) % MOD;
    e = (((b - c) * modinv(q - r) % MOD) + MOD) % MOD;
    d = d * p % MOD;
    e = e * q % MOD;
    return (((d - e) * modinv(p - q) % MOD) + MOD) % MOD;
}

int main() {
    long long N, M;
    cin >> N >> M;
    long long A[N];
    for (int i = 1; i < N; i++) cin >> A[i];
    const auto &res = enum_divisors(N);
    long long count = 0;
    long long ans = 0;
    for (int i = 0; i < res.size(); i++){
        for (int j = 0; j < res.size(); j++){
            if (res[i] == 1 || res[j] == 1) continue;
            if (N == (res[i] * res[j])) continue;
            if (N % (res[i] * res[j]) == 0){
                long long p = A[res[i] - 1] - 1;
                long long q = A[res[i] * res[j] - 1] - 1;
                long long r = A[N - 1] - 1;
                ans = (ans + p_q_r(p, q, r, M)) % MOD;
            }
        } 
    }
    cout << ans << endl;
    long long Q; cin >> Q;
    vector<long long> num[N];
    bool flag[N]; for (int i = 0; i < N; i++) flag[i] = false;
    for (int i = 0; i < Q; i++){
        long long X, Y; cin >> X >> Y;
        if (Y == N){
            const auto &res_ = enum_divisors(X);
            for (int i = 0; i < res_.size(); i++){
                if (res_[i] == 1 || res_[i] == X) continue;
                long long p = A[res_[i] - 1] - 1;
                long long q = A[X - 1] - 1;
                long long r = A[Y - 1] - 1;
                ans = (ans + p_q_r(p, q, r, M)) % MOD;
            }
            for (int i = 0; i < num[X - 1].size(); i++){
                long long p = A[num[X - 1][i] - 1] - 1;
                long long q = A[X - 1] - 1;
                long long r = A[Y - 1] - 1;
                ans = (ans + p_q_r(p, q, r, M)) % MOD;
            }
            flag[X - 1] = true;
        }
        if (Y != N){
            if (N % Y == 0){
                long long p = A[X - 1] - 1;
                long long q = A[Y - 1] - 1;
                long long r = A[N - 1] - 1;
                ans = (ans + p_q_r(p, q, r, M)) % MOD;
            }
            if (flag[Y - 1] == true){
                long long p = A[X - 1] - 1;
                long long q = A[Y - 1] - 1;
                long long r = A[N - 1] - 1;
                ans = (ans + p_q_r(p, q, r, M)) % MOD;
            }
            num[Y - 1].push_back(X);
        }
        cout << ans << endl;
    }
}

yukicoder

結果

テストケース

ソースコード