整除

其中所有数据点都满足
$1 \leq c \leq 50$,$1 \leq t \leq 10^4$,$1 \leq m \leq 10^9$,$1 \leq T \leq 10000$

题解

第一个点 暴力枚举x判断
第二个点 快速幂
第三个点 打表啊孩子
第四个点
就是$x = 0 \pmod p$或者$x = 1 \pmod p$解只有1和p
注意$m$等于$1$的时候要输出$n \pmod {998244353}$
第五个点
既然你都想到一个数了，那么分析一下两个数吧
有两个质数$p_1,p_2$
必须有$x = 0 \pmod {p_1}$或者$x = 1 \pmod {p_1}$成立
必须有$x = 0 \pmod {p_2}$或者$x = 1 \pmod {p_2}$成立
那两两枚举匹配条件考虑一下
假如满足
$x = 0 \pmod {p_1}$，$x = 0 \pmod {p_2}$那么解一定是$p_1p_2$
$x = 0 \pmod {p_1}$，$x = 1 \pmod {p_2}$那么解一定是$kp_1$这个可以用exgcd求
$x = 1 \pmod {p_1}$，$x = 0 \pmod {p_2}$那么解是$gp_2$也可以用exgcd求
$x = 1 \pmod {p_1}$，$x = 1 \pmod {p_2}$那么解一定是1
如果你不想求出所有解，可以直接输出解的个数，4
第六个点到第八个点
刚刚的分析可以有一点启发
我们不就是找了几个中国剩余定理的同余方程算解吗，好像是一组同余方程只在$[1,n]$内有一个解啊
我们只要对于每个质数枚举它范围内x的解，然后把所有解的个数乘起来就行了
第九个点到第十个点
正解你算了算好像要8s？
出题人没良心卡常？？？
积性筛了解一下

PS：我觉得这两个点可能要被小黑屋机子艹翻，但是正常枚举的常数我还是要卡的，积性筛是必须人人都会的，等着之后修改吧

这题作为T1，考察的是人人都会的中国剩余定理和积性筛，知识点清晰，编码难度低，可以说既富有思考的乐趣，又能带来AC的快感，不失为一道好题
用来卡常的分数远远小于NOIP卡常卡的分数，养成常数优化是好习惯，希望大家学会