http://acm.hdu.edu.cn/showproblem.php?pid=1098
其实一开始猜测只要验证 x=1 的时候就行了, 但是不知道怎么证明.
题解表示用数学归纳法, 假设 f(x) 成立, 证明 f(x+1) 成立需要什么条件.
代入之后发现有很多二项式系数, 导致他们都是 65 的倍数, 剩下的恰好就是 f(x) 和 18+ka .
那么只需要找到最小的 a 使得 18+ka 是 65 的倍数.
题解说, 毕竟 65 毕竟小, 可以枚举 a. 因为 a+65 与 a 的对 65 的余数是一样的, 所以只要枚举 0 到 64 就可以了.
我的想法是用扩展欧几里得求这个的解.
首先由裴蜀定理 ax+by=c 有解, 当且仅当 gcd(a,b)|c
那么 18+ka=65t 即 -ka+65t=18 求 a 的最小非负整数解. 套方程的模板.
忘记写解方程的返回值导致返回一个任意值, 有毒.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- // 扩展欧几里得算法: 返回 g=gcd(a,b) , 以及对应的等式 ax+by=g 的解
- ll exgcd(ll a,ll b,ll &x,ll &y) {
- if(!a&&!b)
- return -1;
- if(!b) {
- x=1,y=0;
- return a;
- }
- ll d=exgcd(b,a%b,y,x);
- y-=a/b*x;
- return d;
- }
- bool Liner_qu(ll a, ll b, ll c, ll &x, ll &y) {
- if(a==0) {
- if(b==0) {
- if(c==0) {
- x=0;
- y=0;
- return true;
- } else {
- return false;
- }
- }
- if(c%b==0) {
- x=0;
- y=c/b;
- return true;
- //0x+by=c
- } else
- return false;
- }
- if(b==0) {
- if(c%a==0) {
- x=c/a;
- y=0;
- return true;
- //ax+0y=c
- } else {
- return false;
- }
- }
- ll g=__gcd(a,b);
- if(c%g){
- return false;
- }
- // 裴蜀定理
- ll k=c/g;
- exgcd(a,b,x,y);
- //ax+by=g 的解
- x *= k; // 任意一解
- y *= k;
- ll tx = x;
- x %= b; // 最小解
- if(x<0)
- x += abs(b); // 最小非负整数解
- k=(tx-x)/b;
- y += k*a; // 对应的 y 的解
- return true;
- }
- ll F(int k) {
- int a;
- {
- if(k%5==0||k%13==0)
- return -1;
- else {
- a=1;
- while((k*a+18)%65!=0) {
- a++;
- }
- return a;
- }
- }
- }
- ll G(int k) {
- ll a,b,c,x,y;
- a=-k;
- b=65;
- c=18;
- bool flag=Liner_qu(a,b,c,x,y);
- if(flag) {
- return x;
- } else {
- return -1;
- }
- }
- int main() {
- int k;
- while(cin>>k) {
- ll a,b,c,x,y;
- a=-k;
- b=65;
- c=18;
- bool flag=Liner_qu(a,b,c,x,y);
- if(flag){
- cout<<x<<endl;
- }
- else{
- cout<<"no"<<endl;
- }
- }
- /*for(int k=1; k<=10000; k++) {
- ll s1=F(k);
- ll s2=G(k);
- if(s1!=s2) {
- cout<<"k="<<k<<endl;
- cout<<s1<<endl<<s2<<endl;
- }
- }*/
- }
来源: http://www.bubuko.com/infodetail-3029777.html