题目大意:
给定k,找到一个满足的a使任意的x都满足 f(x)=5*x^13+13*x^5+k*a*x 被65整除
推证:
f(x) = (5*x^12 + 13 * x^4 + ak) * x
因为x可以任意取 那么不能总是满足 65|x
那么必须是 65 | (5*x^12 + 13 * x^4 + ak)
那么就是说 x^12 / 13 + x^4 / 5 + ak / 65 正好是一个整数
假设能找到满足的a , 那么将 ak / 65 分进x^12 / 13 + x^4 / 5中得到 (x^12+t1 ) / 13 + (x^4+t2) / 5 这两项均为整数
那么5*t1+13*t2 = ak
而这里 13|(x^12+t1 ) 5| (x^4+t2)
这里13 , 5均是素数
根据费马小定理可得 x^12 = 1 mod13 x^4 = 1 mod 5
那么t1 = 12 + 13*k1 , t2 = 4 + 5*k2
将t1 t2带入5*t1+13*t2 = ak
那么就是5*(12 + 13*k1) +13*(4 + 5*k2) = ak
->65(k1+k2)+112 = ak
这里k已知 , 求a看做y , k1+k2为整数,看成是x即可
那么就是求65x+ay=-112
这里就是求扩展欧几里得了
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std;10 #define ll long long11 #define N 50012 #define pii pair 13 14 void ex_gcd(ll a , ll b , ll &x , ll &y , ll &d)15 {16 ll t;17 if(b==0){d=a,x=1,y=0;}18 else{19 ex_gcd(b , a%b , x , y , d);20 t=x , x=y , y=t-a/b*y;21 }22 }23 24 25 int main() {26 // freopen("a.in" , "r" , stdin);27 // freopen("out.txt" , "w" , stdout);28 int a;29 while(~scanf("%d" , &a)){30 ll x , y , d;31 ex_gcd((ll)65 , (ll)a , x , y , d);32 if(112%d!=0) puts("no");33 else{34 printf("%I64d\n" , ((112/d*y%65)+65)%65);35 }36 }37 }