提出 #73529319

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll m,a,b;

ll idx(ll x, ll y)
{
    return m*x+y;
}

ll con[1000010], chk[1000010], cnt[1000010];

ll dfs(ll cur)
{
    if (chk[cur]!=0) return cnt[cur];
    chk[cur]=1;
    ll x=cur/m, y=cur%m;
    if (x==0||y==0) {chk[cur]=2; return cnt[cur]=0;}
    ll nxt=con[cur];
    ll ret=0;
    if (chk[nxt]==1) ret=1;
    else if (chk[nxt]==0) ret=dfs(nxt);
    else ret=dfs(nxt);
    chk[cur]=2;
    return cnt[cur]=ret;
}

int main()
{
    ll ans=0;
    cin>>m>>a>>b;
    for (ll i=0;i<m;i++)
    {
        for (ll j=0;j<m;j++)
        {
            ll val=(a*j+b*i)%m;
            con[idx(i,j)]=idx(j,val);
        }
    }
    for (ll i=0;i<m;i++)
    {
        for (ll j=0;j<m;j++)
        {
            if (chk[idx(i,j)]==0) dfs(idx(i,j));
        }
    }
    for (ll i=0;i<m;i++)
    {
        for (ll j=0;j<m;j++)
        {
            ans+=cnt[idx(i,j)];
        }
    }
    cout<<ans;
}

提出情報

提出日時
問題 E - Multiple-Free Sequences
ユーザ prologue1017
言語 C++23 (GCC 15.2.0)
得点 450
コード長 1014 Byte
結果 AC
実行時間 72 ms
メモリ 27052 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 450 / 450
結果
AC × 3
AC × 36
セット名 テストケース
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt
ケース名 結果 実行時間 メモリ
00-sample-01.txt AC 1 ms 3504 KiB
00-sample-02.txt AC 12 ms 8356 KiB
00-sample-03.txt AC 28 ms 27044 KiB
01-01.txt AC 1 ms 3560 KiB
01-02.txt AC 1 ms 3700 KiB
01-03.txt AC 1 ms 3628 KiB
01-04.txt AC 1 ms 3548 KiB
01-05.txt AC 19 ms 26876 KiB
01-06.txt AC 19 ms 27044 KiB
01-07.txt AC 71 ms 26856 KiB
01-08.txt AC 63 ms 26544 KiB
01-09.txt AC 64 ms 26916 KiB
01-10.txt AC 57 ms 25048 KiB
01-11.txt AC 14 ms 22456 KiB
01-12.txt AC 14 ms 22456 KiB
01-13.txt AC 14 ms 22456 KiB
01-14.txt AC 14 ms 22636 KiB
01-15.txt AC 10 ms 16748 KiB
01-16.txt AC 10 ms 16772 KiB
01-17.txt AC 10 ms 16568 KiB
01-18.txt AC 10 ms 16556 KiB
01-19.txt AC 8 ms 12892 KiB
01-20.txt AC 7 ms 12892 KiB
01-21.txt AC 7 ms 12908 KiB
01-22.txt AC 13 ms 20196 KiB
01-23.txt AC 13 ms 20260 KiB
01-24.txt AC 13 ms 20204 KiB
01-25.txt AC 54 ms 21808 KiB
01-26.txt AC 18 ms 10600 KiB
01-27.txt AC 42 ms 19372 KiB
01-28.txt AC 37 ms 16500 KiB
01-29.txt AC 14 ms 9948 KiB
01-30.txt AC 56 ms 24100 KiB
01-31.txt AC 72 ms 27032 KiB
01-32.txt AC 72 ms 26884 KiB
01-33.txt AC 68 ms 27052 KiB