Codeforces 题解集合

发表于 | 分类于 | 阅读次数:
字数统计: 5,615 字

整理历次CF比赛的题解

381

A

题目大意

Alynoa去买书，1、2、3本书套装的售价分别为a、b、c，已知Alynoa手中有n本书，假设他买了k本书后总共拥有的书的数量能够被4整除，求他购买这k本书的最小花费。

思路

  • 一开始想到的就是模拟，分四种情况（需要0/1/2/3本书）进行讨论，需要注意的是除0外的每种情况下都有三种选择，要从这些方案中找到一个最小消耗方案（一开始被hack了）
  • 后面发现可以用DP做（感觉有点大财小用），状态转移方程为 dp[i]=min(dp[i-1]+a,dp[i-2]+b,dp[i-3]+c)

代码

模拟做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve()
{
    long long  n,a,b,c,p,res;
    while(cin>>n)
    {
        cin>>a>>b>>c;
        p=n%4;
        if(p==0)
        {
            cout<<"0"<<endl;
            continue;
        }
        p=4-p;
        if(p==1)
        {
            res=min(a,min(3*c,b+c));
        }
        if(p==2)
            res=min(2*a,min(b,2*c));
        if(p==3)
            res=min(3*a,min(c,a+b));
        cout<<res<<endl;
    }
}

DP 做法：

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
void solve()
{
    long long  n,a,b,c,res;
    long long co[10];
    while(cin>>n)
    {
        res=1e18;
        fill(co,co+9,1e18);
        co[0]=0;  //没买书的花费为0
        cin>>a>>b>>c;
        if(n%4==0)
        {
            cout<<"0"<<endl;
            continue;
        }
        for(int i=0;i<10;i++)   //最多买9本书
        {
            if(i>=1)co[i]=min(co[i],co[i-1]+a);
            if(i>=2)co[i]=min(co[i],co[i-2]+b);
            if(i>=3)co[i]=min(co[i],co[i-3]+c);
            if((n+i)%4==0)res=min(res,co[i]);
        }
        cout<<res<<endl;
    }
}

B

题目大意

给出一些花的魅力值和花的一些组合（给出花魅力值的几个区间），求从这些组合中取出某几个中的花的魅力总数最大。

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of flowers and the number of subarrays suggested by the mother.

The second line contains the flowers moods — n integers a1, a2, …, an ( - 100 ≤ ai ≤ 100).

The next m lines contain the description of the subarrays suggested by the mother. The i-th of these lines contain two integers li and ri (1 ≤ li ≤ ri ≤ n) denoting the subarray a[li], a[li + 1], …, a[ri].

Each subarray can encounter more than once.

思路

  • 将给出的每个区间的花的魅力值相加，如果和为负就舍弃，和为正加入，算出最后的总和

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve()
{
    int n,m,a[101],s[101],res,i,j,x,y;
    while(cin>>n>>m)
    {
        res=s[0]=0;
        for(i=1;i<=n;i++)
        {
            cin>>a[i];
            s[i]=s[i-1]+a[i];
        }
        while(m--)
        {
            cin>>x>>y;
            j=s[y]-s[x-1];
            if(j>0)      //只取和为正的区间
                res+=j;
        }
        cout<<res<<endl;
    }
}

C

题目大意

首先给出mex的定义：在数组中不存在的最小正整数。然后给出一个数组的长度n，和m个子数组区间（起止点），求依据这个信息能够构造的一个数组，使得所有的mex的最小值最大。并输出这个数组。

思路

  • mex不难求，整体的mex最小值也很容易找到（就是所有给出区间长度的最小值+1）。关键是后面数组的构造。
  • 构造数组的方法，假设我们找到的最大的mex最小值为mexi，从数组开始0-mexi不停的循环赋值，因为求得的mexi是最小的并且构造是连续的，凡事数组长度大于mexi的区间都会有0-mex的所有数，这样这个区间就不会出现其mex值比发现的mexi值小的情况。

代码

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
typedef long long ll;

ll a[100005],b[100005];

void solve()
{
    int n,m;
    while(cin>>n>>m)
    {
        ll res=1e10;
        for(int i=0;i<m;i++)
        {
            cin>>a[i]>>b[i];
            res=min(res,b[i]-a[i]+1);     //取最小的mex值
        }
        cout<<res<<endl;
        int tem=0;
        while(n--)     //重复不断地从0-mexi赋值
        {
            cout<<tem<<" ";
            tem++;
            if(tem==res)
                tem=0;
        }
    }
    return;
}

总结

  1. 在理解题意、解题速度方面，英语还是一个很大的障碍。这次比赛就是因为英语，在很多地方对题目的理解都存在偏差。要学好英语
  2. 因为好奇hack是什么，所以A题一过样例就锁定了，结果被hack了还不能改。呜呜呜。。。hack是高手玩的东西，以后不要一过了就锁定题目，要hack也要等快结束了再玩（不过话说那个时候能hack的就已经被hack得差不多了。。。）
  3. 练水题速度、练水题速度、练水题速度。重要的事情说三遍！

390

A

题意

给你一个数组要求将他们进行划分成连续的几个部分，要求每个部分部分不为0

题解

  • 无法划分的情况：数组中的各个都为0
  • 对于剩下的情况，我一开始就只是统一处理：分成两组，第一组从1到最后一个不为0的前面一位，剩下的部分组成第二组。但是后来发现这样做是对于数组总和为0的时候可以，对于数组总和不为0时就是不对的，因为可能有第一组都是0的情况，所以还是要分两种情况讨论
  • 数组总和不为0时，就分成一组
  • 数组总和为0是，分成两组：第一组从1到最后一个不为0的数的前面一位，剩下的组成第二组

代码

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
void solve()
{
	int n;
	while(cin >> n)
	{
		int sum=0,tag=1,u;
		int a[101];
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
			sum+=a[i];
			if(a[i])  //记录最后一个不为0的数字
			{
				u=i+1;
				tag=0;
			}
		}
		if(tag)
		{
			cout<<"NO"<<endl;
			return ;
		}
		if(sum)
		{
			cout<<"YES"<<endl<<"1"<<endl<<"1"<<" "<<n<<endl;
			return ;
		}
		else
		{
			cout<<"YES"<<endl<<"2"<<endl<<"1"<<" "<<u-1<<endl<<u<<" "<<n<<endl;
		}
	}
}

B

题意

题目以小时候玩的井字旗为背景，给出残局，让你求出其中一方是否可以走一步就获得胜利（棋盘大小4*4）

题解

  • 依次考虑每个空格，胜利有两种情况
  • 中间和两边中的一个棋子是自己的，另一个是空格
  • 两个自己的棋子夹一个空格

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
char a[6][6];
char tl[2]={'x','o'};
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

bool judge(int x,int y,int nu)
{
    for(int i=0;i<8;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(a[xx][yy]==tl[nu])
        {
            xx=x-dx[i];
            yy=y-dy[i];
            if(a[xx][yy]=='.')
                return true;
        }
        if(a[xx][yy]=='.')
        {
            xx=xx+dx[i];
            yy=yy+dy[i];
            if(a[xx][yy]==tl[nu])
                return true;
        }
    }
    return false;
}

void solve()
{
    int num1=0,num2=0;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='x')
                num1++;
            if(a[i][j]=='o')
                num2++;
        }
    for(int i=0;i<6;i++)
        a[i][0]=a[0][i]=a[6][i]=a[i][6]='*';
    int be=0;
    if(num2<num1)
        be=1;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
        {
            if(a[i][j]==tl[be]&&judge(i,j,be))
            {
                cout<<"YES"<<endl;
                return;
            }
        }
    cout<<"NO"<<endl;
    return;
}

简洁的代码

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
int dx[]={1,1,1,0,0,-1,-1,-1};
int dy[]={1,0,-1,1,-1,1,0,-1};
char s[10][10];
void check(int i,int j)
{
	for(int k=0;k<8;k++)
	{
		if(s[i+dx[k]][j+dy[k]]=='x'&&s[i+dx[k]*2][j+dy[k]*2]=='x')
		{
			puts("YES");
			exit(0);
		}
		if(s[i+dx[k]][j+dy[k]]=='x'&&s[i-dx[k]][j-dy[k]]=='x')
		{
			puts("YES");
			exit(0);
		}
	}
}
int main()
{
	for(int i=2;i<=5;i++)scanf("%s",s[i]+2);
	for(int i=2;i<=5;i++)for(int j=2;j<=5;j++)if(s[i][j]=='.')check(i,j);
	puts("NO");
	return 0;
}

总结

  • 还是要多练，切水题的时间比较长，不能死在水题上面
  • 看题目不能靠翻译，要锻炼自己的英语水平

391

A

题意

给出一个字符串，求出其中最多能够组成单词“Bulbasaur”的个数（可以将字符串中的字母拆散）

题解

用一个数组记录单词中各个字母的出现次数，出现次数最小的值就是能够组成的单词数

代码

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
void judge(char s)
{
    if(s=='B')con[0]++;
    if(s=='u')con[1]++;
    if(s=='l')con[2]++;
    if(s=='b')con[3]++;
    if(s=='a')con[4]++;
    if(s=='s')con[5]++;
    if(s=='r')con[6]++;
}

void solve()
{
    string s;
    while(cin>>s)
    {
        fill(con,con+7,0);
        for(int i=0;i<s.size();i++)
            judge(s[i]);
        int res=INF;
        for(int i=0;i<7;i++)
        {
            if(i==1||i==4)
                res=min(res,con[i]/2);
            else
                res=min(res,con[i]);
        }
        cout<<res<<endl;
    }
}

B

题意

给出n个数，从这n个数中取出一个组合，使得这个组合中的最大公因子不为1，同时要组合中的数的个数要最大，输出这个组合中的数的个数

题解

  • 首先求出范围内的素数集，然后把每一个素数当成组合中的最大公因子，看这个组合能够有大（看给出的这些数中有多少能够整除当前素数），最后取所有组合的模的最大值
  • 对每一个数进行判断他是否是当前这个素数的倍数这样会造成时间超限，因此采用空间换时间的策略，为数据范围内的每一个数记录其出现次数，然后再将所有能够整除当前素数的值的出现次数进行相加（类似与埃式素数筛选法）

代码

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
39
40
41
42
43
44
45
46
int con[MAX];
bool is_prime[MAX];
int prime[MAX];
int num;

//素数筛选
void init_pri()
{
    num=0;
    memset(is_prime,1,sizeof(is_prime));
    is_prime[0]=is_prime[1]=0;
    for(int i=2;i<MAX;i++)
    {
        if(is_prime[i])
        {
            prime[num++]=i;
            for(int j=i;j<MAX;j+=i)
                is_prime[j]=0;
        }
    }
}

void solve()
{
    int n;
    init_pri();
    while(cin>>n)
    {
        memset(con,0,sizeof(con));
        int x;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            con[x]++;
        }
        int res=1;
        for(int i=0;i<num;i++)
        {
            int tem=0;
            for(int j=prime[i];j<MAX;j+=prime[i])
                tem+=con[j];     //求出当前组合的模
            res=max(res,tem);
        }
        cout<<res<<endl;
    }
}

410

798A - Mike and palindrome

题意

给出一个字符串，判断是否能够只改变一个字符使得这个字符串变成一个回文串

题解

题目要求必须改变一个字符串（一开始被这个坑了），所以把整体分成三种情况，改变一处成为回文串输出YES；已经是回文串并且串的长度是奇数输出YES（因为改变最中间那个字符，这个字符串还是回文串）；其他情况输出NO。

代码

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
void solve()
{
	string s;
	while(cin>>s)
	{
		int n=s.size();
		int u=0;
		if(n==1)
		{
			printf("YES\n");
			return ;
		}
		for(int i=0;i<n;i++)
		{
			if(s[i]!=s[n-1-i])
				u++;
		}
		if(u==2)
			printf("YES\n");
		else if(u==0 && n%2==1)
			printf("YES\n");
		else
			printf("NO\n");
	}
}

798B - Mike and strings

题意

定义对字符串的一个操作：将首字符移到最后。给出n个字符串，问最少进行多少次这样的操作能够使得给出的所有字符串都相同。

题解

模拟法

首先将每一个字符串都复制一遍放到最后，这样左移k位就可以看成是从第k个字符开始长度为len的字符串了。遍历每一个字符串,将其当做目标字符串，计算其他的字符串变成这个字符串的最小开销，求出一个最小值就行了。加上检查是否相等的O(len)的时间复杂度，整体的时间复杂度为O(n^2*len^2)。

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
int n,len;
char s[51][101];

bool judge(char *a,char *b) //判断以a b两个字符串是否相等
{
	for(int i=0;i<len;i++)
		if(a[i]!=b[i]) return false;
	return true;
}

void solve()
{
	while(scanf("%d",&n)!=EOF)
	{
		bool flag=false;
		for(int i=0;i<n;i++)
			scanf("%s",s[i]);
		len=strlen(s[0]);
		for(int i=0;i<n;i++)
			for(int j=0;j<len;j++)
				s[i][j+len]=s[i][j];     //在原来的字符串后面加上相同的字符串
		int res=0,ans=INF;
		for(int i=0;i<n;i++)      //作为基准字符串
		{
			res=0;
			for(int j=0;j<n;j++)
			{
				if(i==j)
					continue;
				int k;
				for(k=0;k<len;k++)
					if(s[i][0]==s[j][k] && judge(s[i],s[j]+k))   //j串循环左移k位
					{
						res+=k;
						break;
					}
				if(k==len)
				{
					printf("-1\n");
					flag=1;
					break;
				}
			}
			if(flag)
				break;
			ans=min(ans,res);
		}
        if(flag) break;
		printf("%d\n",ans);
	}
}

798C - Mike and gcd problem

题意

首先定义对于序列的一个操作：将an 和 an+1的值分别替换为（an-an+1）和（an+an+1）。给出一个序列，问要进行多少步如上的操作才能使得这个序列的最大公因数大于1。

题解

如果两个操作数都是奇数的话，进行一次操作就全部变成偶数；如果两个数是一奇一偶的话，进行一次操作后变成两个都是奇数，再进行一次操作就得到两个偶数。如果一个序列全是偶数的话，他们的最大公因数至少是2，比1大。所以不管序列怎样，一定是有解的。
一个序列如果gcd是1的话那么这个序列中一定存在奇数，并且至少有两个数互质。所以采取将所有的奇数通过操作变换成偶数的方案。我们知道如果是两个奇数要进行一次操作，一奇一偶进行两次操作。

代码

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
39
40
41
42
43
44
45
46
47
48
int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}

int a[maxn];

void solve()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		printf("YES\n");
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		int g=gcd(a[0],a[1]);
		for(int i=2;i<n;i++)
			g=gcd(g,a[i]);
		if(g>1)
			printf("0\n");
		else
		{
			int ans=0;
			for(int i=0;i<n;i++)
			{
				if(!(a[i]&1))   //对奇数进行操作
					continue;
				if(i==n-1)
					ans+=2;
				else
				{
					int tmp=a[i];
					a[i]=a[i]-a[i+1];
					a[i+1]=tmp+a[i+1];
					ans++;
					if(a[i]&1)   //进行两步操作
					{
						tmp=a[i];
						a[i]=a[i]-a[i+1];
						a[i+1]=tmp+a[i+1];
						ans++;
					}
				}
			}
			printf("%d\n",ans);
		}
	}
}

411

A Fake NP

题意

给出一个范围[l,r]，对于所有的从l到r的数的因子数中出现最多的因子数

题解

可以发现除了范围内只有一个数，其他情况2都是出现次数最多的因子数

代码

1
2
3
4
5
6
7
8
9
10
11
void solve()
{
	int l,r;
	while(cin>>l>>r)
	{
		if(l==r)
			cout<<l<<endl;
		else
			cout<<"2"<<endl;
	}
}

B 3-palindrome

题意

要求你创建一个仅含有a、b、c三个字符的长度为n的序列，要求序列中不含有长度为3的回文串,，并且要求含有c字符的数目尽可能少。

题解

“aabb”这样的字符创不断循环就不会含有长度为3的回文串

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
olve()
{
	string st="aabb";
	int n;
	while(cin>>n)
	{
		int d=n/4;
		n%=4;
		for(int i=0;i<d;i++)
			cout<<st;
		for(int i=0;i<n;i++)
			cout<<st[i];
		cout<<endl;
	}
}

C Find Amir

题意

给出编号为1到n的n个点，规定两点(i,j)之间的权值为(i+j)mod(n+1)，求将所有点连接起来的最小代价

题解

  • 最小生成树问题，用贪心思想，发现将第1小的点和第1大的点配对，第2小的点和第2大的点配对，。。。（以此类推可以配对n/2条边）,这样的每次配对的代价都是0
  • 这样两两结对以后（奇数情况下会多出一个点），再将第i大点和第i+1小的点配对，这种配对的每次代价为1。这样就可以生成一棵最小生成树，总体的代价就是后面的配对产生的代价：偶数时候为(n/2-1)，奇数的时候是n/2

代码

1
2
3
4
5
6
7
8
9
10
11
void solve()
{
	int n;
	while(cin>>n)
	{
		if(n%2)
			cout<<n/2<<endl;
		else
			cout<<n/2-1<<endl;
	}
}

D Minimum number of steps

题意

给出一个只含有字符a、b的字符串，规定一次操作为将原字符串的一个’ab’子串转换成’bba’，求转换成最终无法转换的状态要进行的操作次数（对10^9+7取模）

题解

  • 操作完的最终状态应该是所有的字符a都换到了字符串的最后，同时每次操作我们可以看成a向后移动一位的过程，这样的话我们可以计算每个字符a到字符串最后全是a的部分的距离来对于这个a要进行的操作次数。
  • 但是每次a向后移动一位对前面的a是有影响的————每向后移动一位对于前面的a相当于增加了一个b，也就是增加了前面的a到字符串最后的距离。这样我们可以从后往前进行考虑来统一这种影响。
  • 从后往前扫描，用tmp记录中间b的个数，遇到a时累加到ans中同时对tmp加倍（相当于已经将当前的a转移到了最后，这样对于前面的a来说就是增加了tmp个b）。最后的答案就是所有操作的代价ans

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve()
{
	string a;
	while(cin>>a)
	{
		ll tmp=0,ans=0,num=0;
		for(int i=a.size()-1;i>=0;i--)
		{
			if(a[i]=='a')
			{
				ans=(ans+tmp)%MOD;
				tmp=(2*tmp)%MOD;
			}
			else
				tmp++;
		}
		cout<<ans<<endl;
	}
}

小结

  • 看清题意再敲代码，B题就是因为误以为是长度>=3的回文子串而导致错了两发
  • 提高debug水平，D题思路一直对但是因为else分支里面的一个错误导致迟迟没有AC

412

A Is it rated?

题意

给定多个比赛参与者比赛前后的积分，判断这场比赛有没有rated，对rated的定义：至少一个选手的积分发生变化，unrated定义：积分没有变化但是排名发生变化;maybe定义：分数没有变化，排名没变（非递增）

题解

首先判断积分是否发生变化，然后判断是否非递减

代码

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
void solve()
{
	int a[maxn],b[maxn];
	int t;
	while(cin>>t)
	{
		bool flag=1;
		for(int i=0;i<t;i++)
			cin>>a[i]>>b[i];
		for(int i=0;i<t;i++)
		{
			if(a[i]!=b[i])
			{
				cout<<"rated"<<endl;
				flag=0;
				break;
			}
		}
		if(!flag)
			continue;
		for(int i=0;i<t;i++)
		{
			if(i>0&&a[i]>a[i-1])
			{
				cout<<"unrated"<<endl;
				flag=0;
				break;
			}
		}
		if(flag)
			cout<<"maybe"<<endl;
	}
}

B T-Shirt Hunt

题意

给出一个选手这场比赛的排名和当前成绩和这场比赛可能的最差成绩，同时给出一个程序：
i := (s div 50) mod 475
repeat 25 times:
i := (i * 96 + 42) mod 475
print (26 + i)
程序输入一个积分，有25个输出每个输入表示可能的排名，问经过hacks以后达到能够输出当前排名的积分所需要进行成功的hacks次数是多少？

题解

读懂题目这道题非常水，只要以50为单位不断在原来的基础进行加减直到达到符合要求的值，最后输出需要成功的hacks次数就行了

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
bool fun(int s,int p)
{
	int i=(s/50)%475;
	for(int j=0;j<25;j++)
	{
		i=(i*96+42)%475;
		if(26+i==p)
			return true;
	}
	return false;
}

void solve()
{
	int p,x,y;
	while(cin>>p>>x>>y)
	{
		if(fun(x,p))
		{
			//cout<<x<<endl;
			cout<<"0"<<endl;
			continue;
		}
		bool flag=1;
		int tmp=x-50;
		while(tmp>=y)
		{
			if(fun(tmp,p))
			{
				//cout<<tmp<<endl;
				cout<<"0"<<endl;
                flag=0;
				break;
			}
			tmp-=50;
		}
		if(!flag)
			continue;
		tmp=x+50;
		while(tmp)
		{
			if(fun(tmp,p))
			{
				//cout<<tmp<<endl;
                int ans=(tmp-x)/100;
				if((tmp-x)%100!=0) ans++;
				cout<<ans<<endl;
				break;
			}
			tmp+=50;
		}
	}
}

C Success Rate

题意

给出两个分数：x/y p/q，定义两种操作：分子分母同时加上1；分母加上1。问要将前面的分数变成后面的分数要进行的操作数

题解

前面的分数操作到后面的分数y是一定会变成q的倍数的，这样就相当于选择最小的倍数，写一个判断当前倍数是否符合条件的函数，然后再用二分法跑一边就行了，注意特判！

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
bool judg(ll x,ll y,ll p,ll q,ll rate)
{
	if(rate*p>=x && rate*q-y>=rate*p-x)
		return true;
	else
		return false;
}

int fun(ll x,ll y,ll p,ll q,ll l,ll r)
{
	if(l==r) return r;
	if(r==l+1)
	{
		if(judg(x,y,p,q,l)) return l;
		else if(judg(x,y,p,q,r)) return r;
		else return -1;
	}
	//cout<<l<<" "<<r<<endl;
	ll rate=y/q;
	ll m=(l+r)>>1;
	if(judg(x,y,p,q,m)) return fun(x,y,p,q,l,m);
	else return fun(x,y,p,q,m,r);
}

void solve()
{
	int t;
	while(cin>>t)
	{
		ll x,y,p,q;
		for(int id=0;id<t;id++)
		{
			cin>>x>>y>>p>>q;
			if(x*q==p*y)
			{
				cout<<"0"<<endl;
				continue;
			}
			if(p==q || (p==0 && x!=0)) 
			{
                cout<<"-1"<<endl;
				continue;
			}
			ll rate=fun(x,y,p,q,y/q,1e18/q);
			if(rate==-1)
			{
				cout<<"-1"<<endl;
				continue;
			}
            cout<<rate*q-y<<endl;
		}
	}
}