UVA11327 Enumerating Rational Numbers 题解
2021/12/17 23:28:27
本文主要是介绍UVA11327 Enumerating Rational Numbers 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Description
Luogu传送门
Solution
又是一道诈骗题。
观察题目给出的伪代码,不难发现,对于每一个 \(d\),合法的 \(n\) 的个数有 \(\varphi(d)\) 个。
但是 \(k\) 这么大,我们怎么求呢?
继续观察样例,可以发现,样例中给出了 \(k\) 取最大值时的答案。
我们惊讶的发现,分母最大竟然只有 200000 !
所以我们就可以用线性筛筛出 \(2\times10^5\) 以内的 \(\varphi\),并做个前缀和。
对于每一组询问 \(k\),先二分出来小于等于 \(k\) 的最大的数是多少,用 \(k\) 减去它。然后对于当前分母暴力枚举分子,判断二者是否互质即可。
注意:\(\gcd(0, a) = a\),所以有且仅有 \(\gcd(0, 1) = 1\),要特判一下。
另外这题的边界也有一点恶心,建议自己好好思考一下。
Code
关于代码里的各种玄学写法,烦请各位自行模拟一下QwQ
#include <bits/stdc++.h> #define ll long long using namespace std; namespace IO{ inline ll read(){ ll x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); return x; } template <typename T> inline void write(T x){ if(x > 9) write(x / 10); putchar(x % 10 + '0'); } } using namespace IO; const ll N = 2e5 + 10; ll k, tmp, n, d; ll phi[N], sum[N], p[N], tot; bool vis[N]; inline void euler(){ phi[1] = 1; for(ll i = 2; i < N; ++i){ if(!vis[i]) p[++tot] = i, phi[i] = i - 1; for(ll j = 1; j <= tot && i * p[j] < N; ++j){ vis[i * p[j]] = 1; if(i % p[j]) phi[i * p[j]] = phi[i] * (p[j] - 1); else{ phi[i * p[j]] = phi[i] * p[j]; break; } } } phi[1]++; for(ll i = 1; i < N; ++i) sum[i] = sum[i - 1] + phi[i]; } inline ll gcd(ll a, ll b){ return !b ? a : gcd(b, a % b); } signed main(){ euler(); while(scanf("%lld", &k) && k){ if(k == 1) {puts("0/1"); continue;} if(k == 2) {puts("1/1"); continue;} d = upper_bound(sum, sum + N, k) - sum - 1; k -= sum[d++]; if(!k) {printf("%lld/%lld\n", d - 2, d - 1); continue;} for(n = 1; k; ++n) k -= (gcd(n, d) == 1); printf("%lld/%lld\n", n - 1, d); } return 0; }\[\_EOF\_ \]
这篇关于UVA11327 Enumerating Rational Numbers 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求