T1.Crazy

$$\sum\limits_{i=1}^{n}{Fib[i]^2}=\sum\limits_{i=1}^{n-1}{Fib[i]^2}+Fib[n]^2=Fib[n-1]Fib[n]+Fib[n]^2=Fib[n]Fib[n+1]$$

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define MD 1000000007

typedef long long ll;

typedef struct _matrix
{
ll x[3][3];
}matrix;

inline matrix mul(matrix a,matrix b)
{
matrix c;
c.x[1][1]=((a.x[1][1]*b.x[1][1])%MD+(a.x[2][1]*b.x[1][2]%MD))%MD;
c.x[1][2]=((a.x[1][2]*b.x[1][1])%MD+(a.x[2][2]*b.x[1][2]%MD))%MD;
c.x[2][1]=((a.x[1][1]*b.x[2][1])%MD+(a.x[2][1]*b.x[2][2]%MD))%MD;
c.x[2][2]=((a.x[1][2]*b.x[2][1])%MD+(a.x[2][2]*b.x[2][2]%MD))%MD;
return c;
}

inline matrix setmat(ll a,ll b,ll c,ll d)
{
matrix mat;
mat.x[1][1]=a,mat.x[1][2]=b,mat.x[2][1]=c,mat.x[2][2]=d;
return mat;
}

inline matrix ksm(matrix a,ll t)
{
matrix ans;
ans=setmat(1,0,0,1);
while(t)
{
if(t&1)ans=mul(a,ans);
a=mul(a,a);
t>>=1;
}
return ans;
}

inline ll getfib(ll num)
{
if(num==1||num==2)return 1;
matrix but;
but=setmat(1,1,1,0);
but=ksm(but,num-2);
return ((but.x[1][1]+but.x[1][2])%MD);
}

int main()
{
freopen("crazy.in","r",stdin);
freopen("crazy.out","w",stdout);
ll n;
scanf("%lld",&n);
cout<<(getfib(n)*getfib(n+1))%MD<<endl;
return 0;
}


T2.lucky

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

ll L,R,ln,n,un[20];
ll ans;

void input()
{
scanf("%lld%lld%lld%lld",&ln,&n,&L,&R);
for(ll i=1;i<=n;i++)scanf("%lld",&un[i]);
}

ll gcd(ll a,ll b)
{
return (b==0?a:gcd(b,a%b));
}

void sch(ll now,ll pos,ll num)
{
if(now<=0)return;
if(pos==n+1)
{
if(num%2==1)ans+=((R/now)-((L-1)/now));
else ans-=((R/now)-((L-1)/now));
return ;
}
sch(now/gcd(now,un[pos])*un[pos],pos+1,num+1);
sch(now,pos+1,num);
}

int main()
{
freopen("lucky.in","r",stdin);
freopen("lucky.out","w",stdout);
input();
sch(ln,1,1);
cout<<ans<<endl;
return 0;
}



T3.feed

#include <iostream>
#include <cstring>
#include <cstdio>

#define mabs(a) ((a)>0?(a):-(a))

using namespace std;

typedef long long ll;

ll exgcd(ll x,ll y,ll &a,ll &b)
{
if(y==0)
{
a=1;
b=0;
return x;
}
ll ret,tmp;
ret=exgcd(y,x%y,a,b);
a=a-b*(x/y);
swap(a,b);
return ret;
}

ll sa,sb,targ;

void work()
{
ll a,b,g,a0,b0,da,db;
g=exgcd(sa,sb,a0,b0);
if(targ%g){cout<<"BeiJu!"<<endl;return;}
a0*=targ/g;
b0*=targ/g;

da=mabs(sb/g);
db=-mabs(sa/g);

ll dt1,dt2;
dt1=-(a0/da);
dt2=-(b0/db);

ll mans=9999999999;

for(ll i=dt1-1;i<=dt1+1;i++)mans=min(mans,mabs(db*i+b0)+mabs(da*i+a0));
for(ll i=dt2-1;i<=dt2+1;i++)mans=min(mans,mabs(db*i+b0)+mabs(da*i+a0));

cout<<mans<<endl;
}

int main()
{
freopen("feed.in","r",stdin);
freopen("feed.out","w",stdout);
cin>>sa>>sb;
while(cin>>targ)work();
return 0;
}