微信公众号搭建网站,公司网站建设费用计入什么科目,手机网站图片做多大,淘宝网站可信度状况及建设策略【BZOJ5213】[ZJOI2018]迷宫#xff08;神仙题#xff09; 题面 BZOJ洛谷 题解 首先可以很容易的得到一个\(K\)个点的答案。 构建\(K\)个点分别表示\(mod\ K\)的余数。那么点\(i\)的出边\(j\)指向\(i*mj\ mod\ K\)。容易证明这样子一定是可行的。 但是我们显然还有一部分点是…【BZOJ5213】[ZJOI2018]迷宫神仙题 题面 BZOJ洛谷 题解 首先可以很容易的得到一个\(K\)个点的答案。 构建\(K\)个点分别表示\(mod\ K\)的余数。那么点\(i\)的出边\(j\)指向\(i*mj\ mod\ K\)。容易证明这样子一定是可行的。 但是我们显然还有一部分点是可以丢掉的即出现点等价的时候直接合并两个点即可。 那么什么情况下两个点等价呢显然是两个点可以到达的点集相同的时候是可以直接把这两个点给合并的。 考虑一下\(i*m\)在模\(K\)意义下相等的数的个数令\(dgcd(m,K)\)那么合法的取值有\(K/d\)个。定义一个参数\(l\)表示还有\([1,l]\)这些数存在。如果\(lk/d\)那么在范围内可以取遍所有的合法取值那么合并这些之后剩下的部分递归处理这里删去了\(\frac{m}{d}(k-l)\)个合并之后到数。否则如果\(l\le k/d\)或者\(d1\)证明必定两两不等所以这\(l\)个数必须要。 #includecstdio
#includealgorithm
using namespace std;
#define ll long long
ll m,k;int T;
ll Solve(ll l,ll k)
{ll d__gcd(m,k);if(d1||lk/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;
} 转载于:https://www.cnblogs.com/cjyyb/p/10366991.html
