Interesting Integers（CF---BAPC 14 + hnoj11589）扩展欧几里得

题意:类斐波那契；G[k]=G[k-1]+G[k-2];(k>2);使得初始值G[1]和G[2]尽量小（且G[1]<=G[2]）

?

思路：G[3]=1*G[1]+1*G[2];

G[4]=1*G[1]+2*G[2];

G[5]=2*G[1]+3*G[2];

G[6]=3*G[1]+5*G[2];

............... //系数满足fib函数1 1 2 3 5 8 13.......

G[k]=fib[k-2]*G[1]+fib[k-1]*G[2];

?

.......so.由扩展欧几里得求同余方程 a=fib[k-2]、b=fib[k-1];

ax+by=c ( x=G[1],y=G[2],c=G[k])

?

然后注意优化下，求得的最小正整数x，使得y尽量小但是满足y>=x;

?

详见代码;

?

?

用__int64交，long long 会WA

?

#include
  
   
#define ll __int64
#define INF 0x7FFFFFFF
ll fib[55],len;
//用__int64
void init()
{
    fib[0]=0;
    fib[1]=fib[2]=1;
    ll i;
    for(i=3;; i++)
    {
        fib[i]=fib[i-1]+fib[i-2];
        if(fib[i]>1000000000) break;
    }
    len=i;
    // for(i=1;i
   
    = x && y <= yy) { if ((y < yy || (y == yy && x < xx))&&x>0) xx = x, yy = y; x += ma, y -= mb; } } } printf(%I64d %I64d ,xx,yy); } return 0; } 
   
  

?

?