#C240924B. 吃药

标签（Label）

exgcd
数学
动态规划

网址（Website）

题目详情 - 吃药 - Super

题解 - 吃药 - Super

题目（Problem）

详情如下

题目描述

可怜的小 B 在感冒的时候拉了肚子，接下来的 $n$ 天，他每隔至多 $A$ 天就要吃一颗感冒药，每隔至多 $B$ 天就要吃一次腹泻药，但是一天不能同时吃两种药。他想知道，这 $n$ 天至少要吃多少次药。

每隔至多 $x$ 天就要吃药，即这 $n$ 天中不存在连续的 $x$ 天使得小 B 没有吃某一种药。

输入格式

输入一行 3 个正整数 $n, A, B$。

输出格式

输出一行 1 个整数表示答案。

样例

输入数据 1

15 2 3

输出数据 1

[输入输出样例2]

见选手目录下的 drag/drag2.in 与 drag/drag2.ans。

[输入输出样例3]

见选手目录下的 drag/drag3.in 与 drag/drag3.ans。

数据规模与约定

测试包编号	$n \leq$	$A, B \leq$	测试包分值
1	$10^3$	$10^3$	20
2	$10^6$	$10$	30
3	$10^6$	$100$	30
4	$10^6$	$10^6$	20

对于全部数据：$2 \leq A, B \leq n \leq 10^6$。

每个子任务依赖于严格弱于它的子任务。

题解（Solution）

exgcd模板

分类讨论：（ $a$ 代表 $A$ 药的天数，$b$ 代表 $B$ 药的天数，$x$ 代表吃了多少次 $A$ 药，$y$ 代表吃了多少次 $b$ 药）

如果当前两个 $a$ 和 $b$ 的最小公倍数已经大于了 $n$ 了，那么直接以最大天数吃药，一定不会重复，返回计算出来的答案即可；
如果当前 $gcd(a,b)\not = 1$ ，说明在第一次二者天数重合时（即第 $lcm(a,b)$ 天），无论哪一种药早一天吃，他们之后一定不会重天。
证明
$\qquad$由于每次加的数一定是 $gcd(a,b)$ 的倍数，因此保证 $ax\equiv by\equiv gcd(a,b)$ ，如果药 $A$ 提前了一天，那么后面要吃药 $A$ 的天数 $dateA$ 满足 $dateA\equiv gcd(a,b)-1\not \equiv gcd(a,b)$ ，而后面要吃药 $B$ 的天数 $dateB$ 没有变，所以 $dateA\not = dateB$ （药 $B$ 提前一天同理）。
剩下的情况，考虑每次药 $A$ 或者药 $B$ 让了一天，下次还想要相同需要满足什么。假如现在是第 $i$ 天，每次让药 $B$ 让一天，则需要求出一组 $(x,y)$ 使 $-ax+by=1$ 才能再次出现天数相同，将方程转换成 $a(-x)+by=1$ 的形式，通过计算 $\verb!exgcd(a,b,x,y)!$ ，我们可以计算出 $y$ 的最小正整数解，并且算出此时的 $y$ 对应的 $x$ （由于代入负号计算，$x$ 为负数），那么下一个在同一天吃药第 $k$ 天便可以计算得到，由于不知道每次吃的是 $A$ 药还是 $B$ 药，做一个 $dp$ 即可。

出题人题解

$\qquad$当两次吃药重合时，我们会选择一个在前一天吃，枚举是哪一个进行 $DP$，$dp_{i,0/1}$ 表示在 $i$ 放一种药，$i-1$ 放另一种药的最小个数。预处理出下一个在哪里会撞上即可。求解撞上的位置可以用扩展欧几里得求解，如果 $\gcd$ 不为 1，那么以后都不会再相撞，否则进行转移，如果转移后长度超过 $n$ 则统计答案。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;
bool ST;

int n,a,b,f[N][2];

inline int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b,a%b,y,x);
	y -= a / b * x;
	return d;
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("drag.in","r",stdin);
	freopen("drag.out","w",stdout);	
	cin>>n>>a>>b;int Tim = clock();
	int x,y;
	int d = exgcd(a,b,x,y);
	if(a*b/d > n){
		cout<<n/a + n/b<<'\n';
		return 0;
	}
	if(d!=1){
		int tmp = a/d*b;
		cout<<b/d + a/d + min((n-tmp)/a + (n-tmp+1)/b, (n-tmp)/b + (n-tmp+1)/a)<<'\n';
		return 0;
	}
	memset(f,0x3f,sizeof f);
	f[a*b/d][0] = f[a*b/d][1] = a/d + b/d;
	int ans = inf;
	For(i, a*b/d, n){//从他们的lcm开始dp 
		For(j, 0, 1){
			if(f[i][j] == inf) continue;//如果没有提前处理过，说明一定不会落在这一天，跳过
			if(j) swap(a,b), swap(x,y);//保证每次让位的都是b 
			y = (y % a + a) % a;
			x = (1 - y * b) / a;
			int k = i - a*x;
			if(k<=n){
				f[k][j^0] = min(f[k][j^0], f[i][j]+y-x);
				f[k][j^1] = min(f[k][j^1], f[i][j]+y-x);				
			}else ans = min(ans, f[i][j] + (n-i)/a + (n-i+1)/b);
			if(j) swap(a,b), swap(x,y);//换回来 			
		} 
	}cout<<ans<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}