The 2022 ICPC Asia Regionals Online Contest (II)

A Yet Another Remainder

题意

给一个大整数x，再给n行，第i行给i个数，这i个数的第j个数为a[j]+a[j+i]+...+a[j+ki<=n]。再对你进行m次询问，每次给你一个素数p，97>=p>=7,p可以为3。让你给出x%p的结果。

题解

由费马小定理，则当n<=100,第n行的每一个数即为x上每一位数。当n>100时，对于p，则只要找到p-1行，进行下图计算，即可得到结果。

代码

void init()
{
    for (int i = 1; i <= 100; i++)
    {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            c[i][j] = (c[i][j - 1] * 10) % i;
        }
    }
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= min(100,n); i++)
    {
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];
    }
    int m;
    cin >> m;
    if (n <= 100)
    {
        while (m--)
        {
            int p;
            cin >> p;
            int sum = 0;
            for (int i = 1; i <= n; i++)
            {
                (sum = sum * 10 + a[n][i]) %= p;
            }
            cout << sum << endl;
        }
    }
    else
    {
        while (m--)
        {
            int p;
            cin >> p;
            int sum = 0;
            for (int i = 1; i <= p - 1; i++)
            {
                (sum += a[p - 1][i] % p * c[p][(n - i) % (p - 1)]) %= p;
            }
            cout << sum << endl;
        }
    }
}