2057. [ZLXOI2015]殉国

http://cogs.pro/cogs/problem/problem.php?pid=2057

★☆ 输入文件：BlackHawk.in 输出文件：BlackHawk.out 评测插件
时间限制：0.05 s 内存限制：256 MB

【题目描述】

[ZLXOI2015]殉国-LMLPHP

正义的萌军瞄准了位于南极洲的心灵控制器，为此我们打算用空袭摧毁心灵控制器，然而心灵控制器是如此强大，甚至能缓慢控制飞行员。一群勇敢的士（feng）兵（zi）决定投弹后自杀来避免心灵控制。然而自杀非常痛苦，所以萌军指挥官决定到达目的地后让飞机没油而坠落(也避免逃兵)。军官提供两种油：石油和中国输送来的地沟油,刚开始飞机没有油，飞机可以加几桶石油和几桶地沟油(假设石油和地沟油都有无限桶)，飞机落地时必须把油耗尽，已知一桶石油和一桶地沟油所能支撑的飞行距离分别为a,b,驾驶员们必须飞往一个目的地，总距离为c.

1.最少，最多需要加几桶油，若只有一种方案，最少和最多的是相同的.

2.总共有多少种不同的加油配方(死法)能到达目的地。

【输入格式】

只有一行，三个正整数a,b,c

【输出格式】

两行，第一行为最少加几次油和最多加几次油，

第二行为加油方法总数。

若不存在任何方法，第一行输出-1 -1

第二行输出0

【样例输入】

样例1：

2 3 10

样例2：

6 8 10

【样例输出】

样例1：

4 5

2

样例2：

-1 -1

0

【提示】

样例解释：

样例一：飞机加两次石油，两次地沟油，总次数为4，2*2+3*3=10

飞机加五次石油，不加地沟油，总次数为5,2*5+3*0=10

总共两种

样例二：飞机无法到达目的地

数据范围：

对于10%的数据,a<=103,b<=103,c<=103

对于20%的数据,a<=104,b<=104,c<=106

对于50%的数据，a<=109，b<=109,c<=109

对于100%数据，a<=3⋅1018，b<=3⋅1018,c<=3⋅1018

三个答案分值权重分别为20%,30%,50%

首先通过扩展欧几里得求出任意一组解x，y

令g=gcd（a，b），a/=g，b/=g

那么任意解都可以表示成 x-k*b，y+k*a ，k∈Z

那么本题第二问就是问在满足 x-k*b>0，y+k*a>0 的情况下，k的个数

移项得， -y/a < k < x/b

所以解的个数为 floor（x/b）-ceil（-y/a）+1

看第一问

当k增加1，x+y就变成了 x+y+（a-b）

当k加1，x+y 就增加a-b

当k减1，x+y就减少a-b

所以 x+y的最大和最小一定是 k的取值范围的边界

注意用long double

#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long LL;

void read(LL &x)

{

    x=; char c=getchar();

    while(c<'' || c>'') c=getchar();

    while(c>='' && c<='') { x=x*+c-''; c=getchar(); }

}

void exgcd(LL a,LL b,LL &g,LL &x0,LL &y0)

{

    if(!b) { g=a; x0=; y0=; }

    else { exgcd(b,a%b,g,y0,x0); y0-=x0*(a/b); }

}

int main()

{

    freopen("BlackHawk.in","r",stdin);

    freopen("BlackHawk.out","w",stdout);

    LL a,b,c;

    LL g,x0,y0,x,y;

    read(a); read(b); read(c);

    exgcd(a,b,g,x0,y0);

    if(c%g) { printf("-1 -1\n0"); return ; }

    a/=g;

    b/=g;

    x=x0*c/g;

    y=y0*c/g;

    LL s=floor((long double)x/b);

    LL t=ceil((long double)-y/a);

    if(s-t<) { printf("-1 -1\n0"); return ; }

    LL ans1=x+y+(a-b)*s;

    LL ans2=x+y+(a-b)*t;

    printf("%lld %lld\n%lld",min(ans1,ans2),max(ans1,ans2),s-t+);

}

COGS