【BZOJ5213】[ZJOI2018]迷宫(神仙题)
2024-10-13 06:58:26
【BZOJ5213】[ZJOI2018]迷宫(神仙题)
题面
题解
首先可以很容易的得到一个\(K\)个点的答案。
构建\(K\)个点分别表示\(mod\ K\)的余数。那么点\(i\)的出边\(j\)指向\(i*m+j\ mod\ K\)。容易证明这样子一定是可行的。
但是我们显然还有一部分点是可以丢掉的,即出现点等价的时候,直接合并两个点即可。
那么什么情况下两个点等价呢?显然是两个点可以到达的点集相同的时候是可以直接把这两个点给合并的。
考虑一下\(i*m\)在模\(K\)意义下相等的数的个数,令\(d=gcd(m,K)\),那么合法的取值有\(K/d\)个。定义一个参数\(l\)表示还有\([1,l]\)这些数存在。如果\(l>k/d\),那么在范围内可以取遍所有的合法取值,那么合并这些之后,剩下的部分递归处理,这里删去了\(\frac{m}{d}(k-l)\)个合并之后到数。否则如果\(l\le k/d\),或者\(d=1\),证明必定两两不等,所以这\(l\)个数必须要。
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
ll m,k;int T;
ll Solve(ll l,ll k)
{
ll d=__gcd(m,k);if(d==1||l<=k/d)return l;
if(k<=(double)m*(k-l))return k/d;
return m/d*(k-l)+Solve((k-m*(k-l))/d,k/d);
}
int main()
{
scanf("%d",&T);
while(T--)scanf("%lld%lld",&m,&k),printf("%lld\n",Solve(k-1,k)+1);
return 0;
}
最新文章
- Android 高级面试题及答案
- 【目录】processing
- BZOJ 2467 解题报告
- redis-key2
- 关于登录的会话控制, 终极解决方案 - chunyu
- android中广播接收SD卡状态
- ENOVIA 基础
- 《JavaScript高级程序设计》读书笔记 ---基本类型和引用类型的值
- [转载] python利用psutil遍历进程名字和exe所在目录
- 用一条SQL语句查出每门课都大于80分的学生的姓名
- 《你必须掌握的Entity Framework 6.x与Core 2.0》书籍出版
- C#+EntityFramework编程方式详细之Model First
- Thinkpad 小红点飘移的不完美解决办法
- App测试流程及测试点(个人整理版)
- Codeforces Round #523 (Div. 2) B Views Matter
- 【php增删改查实例】第二十一节 - 用户修改功能
- 微信公开课厦门站 时尚行业专场PPT
- pom.xml实例
- 数据结构(C语言版)-第3章 栈和队列
- handler通信机制