【数学小考 3】 2015.07.12

考得一般==原以为能AK

我的疯狂被屠

[Description]

求斐波那契数列平方的前缀和sum[n],如sum[4]=(fab[1]^2+fab[2]^2+fab[3]^2+fab[4]^2)=15。

[Hint]

$n≤10^{15},答案对 1000000007 取模$

[Solution]

打表发现规律,sum[n]=fab[n]*fab[n+1](证明略),然后矩阵乘法就可以了。
考试第一次写重载运算符竟然没挂(然而代码块好像坏了?!)–

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstring>
using namespace std;

typedef long long ll;
const int mod=1000000007;

struct matrix{
int m[2][2];
void init(){ m[0][0]=0; m[0][1]=m[1][0]=m[1][1]=1; }
matrix operator * (const matrix b) const {
matrix k;
k.m[0][0]=((ll)m[0][0]*b.m[0][0]%mod+(ll)m[0][1]*b.m[1][0]%mod)%mod;
k.m[1][0]=((ll)m[1][0]*b.m[0][0]%mod+(ll)m[1][1]*b.m[1][0]%mod)%mod;
k.m[0][1]=((ll)m[0][0]*b.m[0][1]%mod+(ll)m[0][1]*b.m[1][1]%mod)%mod;
k.m[1][1]=((ll)m[1][0]*b.m[0][1]%mod+(ll)m[1][1]*b.m[1][1]%mod)%mod;
return k;
}
};

void pow(matrix&k,ll n){
matrix ans; ans.init();
while(n){
if(n&1) ans=ans*k;
k=k*k; n>>=1;
}
k=ans;
}

int main(){
ll n;
scanf("%lld",&n);
matrix a,b;
a.init(); b.init();
pow(a,n); pow(b,n+1);
printf("%lld",(ll)a.m[0][0]*b.m[0][0]%mod);
return 0;
}

我的数字选取

[Description]

给出1个数幸运数x和若干个(小于等于15)倒霉数y1-yk,求区间[L,R]之间有多少个数能被x整除但不会被任何一个y整除。

[Hint]

$0≤L≤R≤10^{15}$

[Solution]

容斥原理。ans=所有能被x整除的数-(所有能被x和一个y的公倍数整除的数)+(所有能被x和两个y的公倍数整除的数)…
暴力枚举即可。
区间[L,R]内能被k整除的数即为L/k-(R-1)/k。
时刻防溢出qwq

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>

typedef long long ll;
ll l,r,ans;
ll ln,uln[15],cnt;

ll gcd(ll x,ll y){ return !y?x:gcd(y,x%y); }

bool choose[15];
void check(){
ll num=ln,sum=0;
for(int i=0;i<cnt;i++) if(choose[i]){
sum++;
ll k=gcd(num,uln[i]);
num=(double)num*uln[i]/k;
}
ans+=(sum%2?-1:1)*((r/num)-((l-1)/num));
}
void search(int t){
for(int i=0;i<2;i++){
choose[t]=i;
if(t==cnt-1) check();
else search(t+1);
}
}

int main(){
scanf("%lld%lld%lld%lld",&ln,&cnt,&l,&r);
for(int i=0;i<cnt;i++) scanf("%lld",&uln[i]);
if(cnt) search(0);
else ans=r/ln-(l-1)/ln;
printf("%lld",ans);
return 0;
}

我的喂养计划

[Description]

在方程ax+by=c的所有解对{x,y}中,min{|x|+|y|}值。

[Hint]

多组数据(不超过1000组),$a,b,c≤10^{6}$

[Solution]

$f(x)=|x|+|y|=|x|+|(c-ax)/b|$
根据折线函数的性质,此函数有两个极小值,,分别在x=0,x=c/a处取到,因为要求正整数,只需判断这两个极小点附近的四个值即可。
再次:时刻防溢出qwq

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;

void exgcd(ll a,ll b,ll&d,ll&x,ll&y){
if(!b) d=a,x=1,y=0;
else{ exgcd(b,a%b,d,y,x); y-=x*(a/b); }
}

int main(){
ll A,B,n; scanf("%lld%lld",&A,&B);
while(~scanf("%lld",&n)){
ll d,x,y,ans=0x7fffffff;
exgcd(A,B,d,x,y);
if(n%d){ printf("BeiJu!\n"); continue; }
x*=n/d; y*=n/d;
ans=min(ans,abs(x)+abs(y));
x=(x%(B/d)+(B/d))%(B/d)-(B/d);
y=(n-x*A)/B;
ans=min(ans,abs(x)+abs(y));
x+=B/d;
y=(n-x*A)/B;
ans=min(ans,abs(x)+abs(y));
printf("%lld\n",ans);
}
return 0;
}

Summary

时刻记得防溢出(重要的事说三遍)