#PQJ1193x6179. QOJ 1193_6179

    ID: 2566 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:FJOI 2022

QOJ 1193_6179

给定一个一元二次函数 𝑓 ( 𝑥 )

𝑎 𝑥 2 + 𝑏 𝑥 + 𝑐 。对于满足 1 ≤ 𝑖 ≤ 𝑛 的 𝑛 个正整数 𝑖 ,相应的二次函数值分别为 𝑓 ( 1 ) , 𝑓 ( 2 ) , ⋯ , 𝑓 ( 𝑛 ) 。在通常情况下,它们的乘积 ∏ 𝑖

1 𝑛 𝑓 ( 𝑖 ) 不是一个平方数。能整除这个乘积的最大平方数是多少呢?

最大平方数问题:对于给定的一元二次函数 𝑓 ( 𝑥 )

𝑎 𝑥 2 + 𝑏 𝑥 + 𝑐 ,计算出能整除 ∏ 𝑖

1 𝑛 𝑓 ( 𝑖 ) 的最大平方数。

输入格式

输入的第一行有四个整数 𝑎 , 𝑏 , 𝑐 , 𝑛 , ,分别表示给定的一元二次函数 𝑓 ( 𝑥 )

𝑎 𝑥 2 + 𝑏 𝑥 + 𝑐 的相应系数为 𝑎 , 𝑏 , 𝑐 ,以及乘积的项数为 𝑛 。

输出格式

输出能整除 ∏ 𝑖

1 𝑛 𝑓 ( 𝑖 ) 的最大平方数,对 998 244 353 取模的结果。

样例数据 样例输入 1 2 3 4 样例输出 2916 子任务

测试数据中 100 % 的数据满足 1 ≤ 𝑎 , 𝑛 ≤ 2 × 10 5 , 0 ≤ 𝑏 , 𝑐 ≤ 2 × 10 5 。