牛客练习赛111

牛客练习赛111_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

简单的数学题

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

小红最近沉迷于数学题，她现在想考考小明一道简单的数学题：

给定正整数 mmm，xxx ，小红定义一个正整数 yyy 和 xxx 具有关于 mmm 的等价关系，则 yyy 满足：

使得对于正整数 k=1，2 ... 10100k=1，2\ ...\ 10^{100}k=1，2 ... 10100，当 kx⩽mkx \leqslant mkx⩽m 时，ky⩽mky \leqslant mky⩽m。当 kx>mkx > mkx>m 时，ky>mky > mky>m 。

小红想知道有多少个正整数 yyy ，yyy 和 xxx 具有关于 mmm 的等价关系？

输入描述:

输入共 T+1T+1T+1 行。

第一行一个整数表示 T (1≤T≤105)T \ (1≤T≤10^5)T (1≤T≤105)。

接下来 TTT 行，每行 222 个正整数，m, x (1≤x≤m≤109)，m,x如上描述。m,\ x \ (1 ≤ x ≤ m ≤ 10^9) ，m,x如上描述。m, x (1≤x≤m≤109)，m,x如上描述。

输出描述:

输出共 TTT 行，每行一个整数，表示多少个正整数 yyy 和 xxx 具有关于 mmm 的等价关系。

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int m, x;cin >> m >> x;int d = m / x;printf("%d\n",m / d - m / (d + 1));
}signed main()
{int T = 1;cin >> T;while (T--){solve();}return 0;
}

D 青蛙兔子的约会

每当晚上时，青蛙都会出来活动，白天休息。白天时，兔子就会出来活动，晚上休息。

青蛙一次可以跳 aaa 米，兔子一次可以跳 bbb 米，已知青蛙在坐标 000 的位置，兔子在坐标 nnn 的位置。

现在青蛙与兔子在明天白天有个约会，但是青蛙不想等太久兔子，他决定在今天夜晚时就开始行动。

但是青蛙又怕累，所以晚上时青蛙只会向兔子的方向跳 [L,R][L,R][L,R] 次。

问青蛙能否与兔子约会？

输入描述:

输入共 T+1T+1T+1 行。

第一行一个整数表示 T (1≤T≤105)T\ (1≤T≤10^5)T (1≤T≤105)。

接下来 TTT 行，每行 555 个整数表示 a,b,n,L,R(1≤a,b,n,L,R≤109,L≤R)a,b,n,L,R (1≤a,b,n,L,R≤10^9,L ≤ R)a,b,n,L,R(1≤a,b,n,L,R≤109,L≤R)。

数据保证青蛙不会跳过nnn的位置，即 1≤La≤Ra≤n1≤ La≤ Ra ≤ n1≤La≤Ra≤n 。

输出描述:

输出共 TTT 行，每行一个"YES" 或 "NO"（不包括双引号），表示青蛙和兔子能否约会。

解题思路:

其一:最简单的无脑创暴力解

#include<bits/stdc++.h>
using namespace std;
#define long long int 
int  a , b , n , L , R, T;
signed main()
{cin >> T;while(T--){cin >> a >> b >> n >> L >> R;int i = R;for(i; i >= L ;i--){if((n - (a * i)) % b == 0){cout << "YES" << endl;break;}}if(i == L - 1)cout << "NO" << endl;}return 0;
}

当然面对10e9的数量级是肯定噶了

其二:

裴蜀定理应用

问题转换

输入 a b n L R

求[L,R]区间是否存在一个K使得

(n - K * a) % b == 0

#include <bits/stdc++.h>
using namespace std;
/*
裴蜀定理应用
问题转换
输入 a b n L R
求[L,R]区间是否存在一个K使得
(n - K * a) % b == 0
*/
//#define  long long int;
long long a, b, n, L, R, T;
long long exgcd(long long a, long long b, long long& x, long long& y) {if (b == 0) {x = 1, y = 0;return a;}long long d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main() {cin >> T;while (T--){cin >> a >> b >> n >> L >> R;long long d, x, y;d = exgcd(a, b, x, y);if (n % d != 0) {cout << "NO" << endl;continue;}long long k = n / d;x *= k;y *= k;long long  lb = (L - x) / b;if ((L - x) % b != 0) lb++;long long rb = (R - x) / b;if ((R - x) % b != 0) rb--;lb <= rb ? cout << "YES" << endl : cout << "NO" << endl;}return 0;
}

当然我写错了,通过率更低了

正解等我把 裴蜀定理应用再学深一点再解决,鸽一会