题解

题目类型：区间 + 同余判定的可达性判断；多组数据的在线生成与统计
核心思路：把“可达”的 (X) 定义成若干区间条件与整除（同余）条件的并集。对每组 ((K,M,X))，逐一测试是否落入这些集合；若可达则计数 tot++。测试结束后，按照给定的三条二次同余递推式更新 (K,M,X)，继续下一组。

一、输入与总体流程

• 首行一次性读入：
  T, a, b, c, d, K, aa, bb, cc, dd, M, aaa, bbb, ccc, ddd, X
  其中 T 为组数；后续参数用于产生新一组 ((K,M,X)) 的递推。
• 对每组数据：
  1. 用当前的 (K,M,X) 做一次判断（若满足可达条件 tot++）。
  2. 用下列三条式子更新到下一组： [ \begin{aligned} K &\leftarrow \big(a,(K^2\bmod d)+bK+c\big)\bmod d + 20 \ M &\leftarrow \big(aa,(M^2\bmod dd)+bbM+cc\big)\bmod dd + 20 \ X &\leftarrow \big(aaa,(X^2\bmod ddd)+bbbX+ccc\big)\bmod ddd \end{aligned} ]
• 最后输出累计答案 tot。

递推式的形态与二次同余随机数生成器类似，+20 保证 K,M 不小于 20。

二、判定规则（与代码一一对应）

设 xx = X - i*M 为从 (X) 中扣去若干个 (M) 后的剩余量。程序将“可达”的情形划分为层层递进的多个充分条件，一旦命中即认为本组计数：

1）第一层（最强的几类）——直接对 (X) 与 (X-2M) 检查

• 命中以下任一条件视为可达（tot++）：
  1. (X = 8K)
  2. (2 \le X \le 8K-2)
  3. 令 (xx = X-2M)，则 (0 \le xx \le 5K-2)
  4. (xx = 5K)
  5. (xx \equiv 0 \pmod 3) 且 (0 \le xx \le 6K)

这一层把 (X) 放在若干连续区间及等差（模 3）子集上检验；若满足，直接判为可达。

2）第二层——从 (X) 中扣去 (i\in{2,3,4}) 个 (M) 再看

• 对每个 (i=2,3,4)，令 (xx=X-iM)。若出现以下任意一种，则可达：
  • (0 \le xx \le K)（任意整值）
  • (0 \le xx \le 2K) 且 (xx) 为偶数
  • (0 \le xx \le 3K) 且 (xx \equiv 0 \pmod 3)

3）第三层——从 (X) 中扣去 (i\in{0,1,2,3,4}) 个 (M)，看能否落在“偶数段”

• 对每个 (i=0,1,2,3,4)，令 (xx=X-iM)。若 [ 2\le xx\le 2K \quad\text{且}\quad xx\equiv 0\pmod 2 ] 则可达。

4）第四层——看 (X) 是否就是某个小倍数的 (M)

• 若存在 (i\in{0,1,2,3,4}) 使 (X=(2+i)M)（即 (2M,3M,4M,5M,6M)），则可达。

5）第五层——从 (X) 中扣去 0~2 个 (M) 后，落在“长区间”

• 对 (i=0,1,2)，令 (xx=X-iM)。若满足 [ 2\le xx\le 5K-2 \quad\text{或}\quad xx=5K ] 则可达。

以上是一系列覆盖集合的并集。程序按层短路判断：只要命中任意一层即可，不再继续更弱的条件。

三、正确性直观解释

可以把这些条件理解为：
把 (X) 通过扣去若干个 (M) 的方式，尝试落在由 (K) 划定的若干可构造段上（如 ([0,K])、偶数段 ([0,2K]\cap 2\mathbb{Z})、3 的倍数段 ([0,3K]\cap 3\mathbb{Z}) 以及更长区间 ([2,5K-2]) 等），或直接判断 (X) 是否等于 (2M,3M,\dots) 的几种小倍数。
这些条件共同构成了“可达集合”的充分覆盖：为尽可能以 (O(1)) 的代价完成一次判断，不做搜索/DP，仅用简单区间与整除检验即可定性。

四、实现细节

• 变量均用 long long（其中循环变量也用寄存器声明，符合原代码写法）；
• 一次命中后直接 tot++；未命中则进入下一层更宽松的条件；
• 每组处理完毕后，用给定递推式更新 (K,M,X)，继续下一组。
• 最终输出 tot。

五、复杂度

• 每组数据都是常数次判断，时间复杂度 (O(1))；
• 总体复杂度 (O(T))，空间 (O(1))（不计输入输出）。

代码（与题给一致）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
//freopen("test.in","r",stdin);freopen("test.ans","w",stdout);
    register ll T,a,b,c,d,aa,bb,cc,dd,aaa,bbb,ccc,ddd,K,M,X,tot=0,xx; register bool good;
    cin >> T >> a >> b >> c >> d >> K >> aa >> bb >> cc >> dd >> M >> aaa >> bbb >> ccc >> ddd >> X;

    while(T--){
        xx = X - 2ll * M;
        if(  ( X == 8*K ) || ( 2 <= X && X <= 8ll*K-2 ) || ( 0 <= xx && xx <= 5ll*K-2 ) || ( 5ll*K == xx ) || ( xx % 3 == 0 && xx <= 6ll * K && xx >= 0 )){
            tot++;// 3+3+2  3+3+2M
        }else{
            good = false;
            for( register ll  i = 2; i <= 4; i++ ){
             // M,2M + 3 + 2M
                xx =  X - i * M;
                if( ( 0 <= xx && xx <= K ) || ( 0  <= xx && xx <= 2*K &&  xx % 2 == 0  ) || ( 0 <= xx && xx <= 3*K && xx % 3 == 0 ) ){
                    good = true;
                    break;
                }
            }
            if(good) tot++;
            else{
                for(register ll i = 0; i <= 4; i++ ){// M,2M + M,2M + 2
                     xx = X - i * M;
                     if( 2 <= xx && xx <= 2 * K && xx % 2 == 0 ){
                        good = true;
                        break;
                     }
                }
                if(good) tot++;
                else{
                    for(register ll i = 0; i <= 4 ; i++ ){// M,2M + M,2M + 2M
                        if( (2+i) * M == X){
                            good = true;
                            break;
                        }
                    }
                    if(good) tot++;
                    else{
                        for(register ll i = 0 ; i <= 2; i++ ){ //M,2m + 3 + 2
                            xx = X -  i * M;
                            if( (2 <= xx && xx <= 5 * K - 2) || xx == 5 * K  ){
                                good = true;
                                break;
                            }
                        }
                        if(good) tot++;
                    }
                }
            }
        }
        K = ( (a * ((K*K)%d))%d + b * K + c ) % d + 20ll;
        M = ( (aa * ((M*M)%dd))%dd + bb * M + cc ) % dd + 20ll;
        X = ( (aaa * ((X*X)%ddd))%ddd  + bbb * X + ccc ) % ddd + 20ll; // 若与你本地代码不一致，请保持你原始版本
    }
    cout << tot ;
    return 0;
}