题解 P3923 【大学数学题】

解法0： 学习⑨。。等等，去哪学习⑨ 期望得分：0分 解法1： 输出-1 期望得分：10分 解法2： 暴力写一个程序搜索小数据 时间复杂度O(反正n=8跑不完) 期望得分：15分 解法3： 对于n为质数情况直接输出mod n的结果 时间复杂度O(n^2) 期望得分：25分 解法4： 找规律，发现只有两个点不能表示成p^k的形式（p为质数，k为正整数） 使用解法1后发现正好有两个点通过了 于是果断在这两个点输出-1，并综合前面做法 期望得分：40分 解法5： 设n=p^k，猜想一定存在 将有限域中的数看做一个mod p意义下的k次多项式，每项为p进制下对应位 加法很自然就能完成 乘法需要找到一个mod p意义下的k次不可约多项式，将两个多项式乘完后取除以该不可约多项式的结果 最后转化为10进制数输出 时间复杂度O(反正一秒内跑得完) 期望得分：40~100分（取决于能手玩出多少不可约多项式）（好像不可约多项式也可以爆搜出来？） 不给标程啦