Jennie 素数不多，我们考虑素数就可以了 对于素数来说，能以他为gcd，那么肯定时它的倍数，且$gcd(frac{i}{prime},frac{j}{prime})=1$，那么我们先求出$1-n$有多少个prime的倍数，然后取出两个互质的倍数，就是一个答案 这不就时$phi()$的干的好事 最后求个和，处理一下. #include<io…

Jennie 首先我们要知道欧拉定理 $a^bequiv^{b%phi(p)+phi(p)}quad b>=p$ $a^bequiv^{b%phi(p)} quad b<p$ 然后对于这个式子，我们可以改造成 $2^{2^{2^{2^{...}}}%phi(p)+phi(p)}$ 显然肯定是满足1的 然后这样p就成了$phi(p)$ 直…

https://www.cnblogs.com/bzy-blog/p/14353073.html

Jinsoo 用更相减损术写的 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define int long long using namespace std; long long a,b,c; l…

Jennie 似乎对于每一个不等式，都是有一个阈值k，那么分类讨论a的符号，也就是不等式的方向，因为输入的key的大小不超过$10^6$，那么一些算出来的key可以知道肯定满足、不满足 然后呢，根据不等式的方向扔到两个树状数组，查询即可 #include<iostream> #include<cstdio> #include…

Archie 建反图，dfs #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int n,m; int x,y; struct e{ int to; int n…

Jisoo tarjan求割边 对于一条$(u,v)$，如果他是割边，那么v子树中一定有一个点s$low_s>dfn_u$ 然后改造一下搜索函数 #include<iostream> #include<cstdio> #include<algorithm> #include<stack> usi…

Jisoo 如果这玩意成不了二分图，肯定有环，而且还是肯定有一个三元环 如果一个点到两个点的距离$>k$那么这两个点之间的距离一定大于k 那么我们只要确定存不存在这样的三元组就可以了 怎么确定呢 画图可得，如果有三元环，那么这个三元环一定会存在一种包括两端点的情况 然后就显然我们要找直径，检查每一个点到这两端点的距离 #include<…

Jennie 每个单词只有两个字符，那么就在这两个字符之间连一条边。 最后n+1个字符，显然是所有单词只出现了一遍 这样我们的目标就是找一条欧拉路径就可以了 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; i…

Rose $O(sqrt n)$也是可以接受的对吧 化简式子得$gcd(frac{x}{a_1},frac{a_o}{a_1})=1$和$gcd(frac{b_1}{x},frac{b_1}{b_0})=1$ 然后枚举$b_1$的因子就可以了 #include<iostream> #include<cstdio> #incl…