CF1877C Joyboard

One_JuRuo · 2023-10-09 10:01:39 · 题解

思路

一个比较明显的结论是，不同的数字个数只可能是 1,2,3。

可以随手写一个暴力的输出程序，假定 n 和 m，把所有可能的序列都输出来，就可以发现这个规律。

也可以感性思考一下。

如果第 n+1 位是 0，那么整个序列都会是 0，个数也就是 1。

如果第 n+1 位是一个小于 n 的数 x_0，那么就会重复若干次 x_0，在第 x_0 位开始变为 0，所以这种情况的个数是 2。

如果第 n+1 位是一个 n 的倍数 x_1，那么只会出现一次 x_1，此后都是 0，这种情况的个数也是 2。

其他情况就是不是 n 的倍数并且大于 n 的情况，假设填的是 x_2，那么第 n+1 位是 x_2，第 n 位就是 x_2 \bmod n，重复若干次后直到遇到第 x_2 \bmod n 位，就会变为 0，因为 x_2 不是 n 的倍数，所以一定会有三个不同的数字。

所以如果要求的数量大于 3 就无解，即为 0。

如果要求的数量是 1，只有一种情况。

如果要求的数量是 2，情况数就是 n-1+\lfloor \frac m n\rfloor。

如果要求的数量是 3，情况数就是 m+1-1-(n-1+\lfloor \frac m n\rfloor)=m-n+1+\lfloor \frac m n \rfloor。

需要注意 m<n 的情况，这种情况时，数量为 2 的答案就是 m，数量为 3 的答案是 0。

AC code

#include<bits/stdc++.h>
using namespace std;
long long T,a,b,c;
int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        if(c>3) puts("0");
        else
        {
            if(c==1) puts("1");
            else if(c==2) printf("%lld\n",min(b,a-1+b/a));
            else printf("%lld\n",max(0ll,b-a+1-b/a));
        }
    }
    return 0;
}