4736: 计算(广东省重点中学信息学邀请赛提高组)
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
广东省重点中学信息学邀请赛(GDKOI 2024 day2提高组第二试)
定义F(x,a,b)=gcd(xa−1,xb−1)+1,x>0。
特别的，如果a=0或b=0,F(x,a,b)=0。
现在给出五个非负整数m,a,b,c,d。
令L=F(m,a,b)+1,R=F(m,c,d)。
问集合{L,L+1,L+2,...,R−2,R−1,R}有多少个子集和是m的倍数。
由于答案可能很大，你只需要输出方案数对998244353取模后的结果就可以了。
定义F(x,a,b)=gcd(xa−1,xb−1)+1,x>0。
特别的，如果a=0或b=0,F(x,a,b)=0。
现在给出五个非负整数m,a,b,c,d。
令L=F(m,a,b)+1,R=F(m,c,d)。
问集合{L,L+1,L+2,...,R−2,R−1,R}有多少个子集和是m的倍数。
由于答案可能很大，你只需要输出方案数对998244353取模后的结果就可以了。
输入
输入第一行为一个整数T，表示数据组数。
接下来一行T行，每行五个非负整数m, a,b,c,d。
接下来一行T行，每行五个非负整数m, a,b,c,d。
输出
对于每组数据，输出答案。
样例输入 复制
3
5 0 0 2 1
4 1 2 2 4
8 3 2 4 6样例输出 复制
8
1024
527847872提示
样例解释：
经过计算可知 L=1，R=5，集合是1,2,3,4,5，满足条件的子集和有以下 8 个：
{}{5}{2,3}{1,4}{1,2,3,4}{2,3,5}{1,4,5}{1,2,3,4,5}
经过计算可知 L=1，R=5，集合是1,2,3,4,5，满足条件的子集和有以下 8 个：
{}{5}{2,3}{1,4}{1,2,3,4}{2,3,5}{1,4,5}{1,2,3,4,5}