1 해설
-
0
题意
给定 ,求 的最小正整数解。
Solution
先考虑平凡的做法。
从 枚举到 ,每一个都跑一次扩展欧几里得,时间复杂度 ,一看数据范围 ,可以考虑丢掉这种算法。
既然没办法用同余方程解决,那我们考虑将 变成减法的形式。
其中那个 是个整数。我们只要求出这个 就能求出 。
现在移项,得到:
求 的话我们就不能出现 。尝试取模,同时 可以消去 ,得到:
ohhhhhhhhh!这个形式跟我们的 是完全一致的!所以我们可以考虑使用递归求解。
设有函数 求解的是 中 的最小正整数解,那么我们递归进去就应该是 。注意,因为取模的可乘性,所以 是可以 的。
这个函数的复杂度显然是正确的,与辗转相除有异曲同工之妙。
写的时候注意向下取整的问题,不然你会像我这样一直差 ,急的像个猴子:link。
代码:
#include<bits/stdc++.h> #define ll long long using namespace std; int T; ll solve(ll d, ll m, ll l, ll r){ if(!d || l > r) return -1; ll x = (l - 1) / d + 1; if(x * d <= r) return (x % m + m) % m; ll p = solve(m % d, d, ((-r) % d + d) % d, ((-l) % d + d) % d); if(p == -1) return -1; return ((((l - 1) + m * p) / d + 1) % m + m) % m; } int main(){ scanf("%d", &T); while(T--){ ll m, d, l, r; scanf("%lld%lld%lld%lld", &m, &d, &l, &r); r = min(m - 1, r); printf("%lld\n", solve(d, m, l, r)); } return 0; }
- 1
정보
- ID
- 1421
- 시간
- 1000ms
- 메모리
- 256MiB
- 난이도
- 10
- 태그
- (N/A)
- 제출 기록
- 16
- 맞았습니다.
- 1
- 아이디