在颓废了一天之后决定写一个题解.因为我觉得这题挺有意思. 我们需要转化一下式子.把原来的a,b改成A,B.设d=gcd(A,B),A=ad,B=bd. 那么(a+b)d | abd2,即(a+b)|ab*d. 又因为gcd(a,b)=1,所以(a+b)一定与a,b都互质.于是(a+b)|d. 设t*(a+b)=d.那么因为bd≤n,所以t(a+b)*b≤n.那么b是sqrt(n)级别的.且我们只需要统计三元组(a,b,t)的个数就行了. answer=∑b∑a(n/b)/(a+b)(gcd(a,b)=1)然后这个玩意看上去好像是个长得怪异一点的狄利克雷卷积啊. 于是就是要求[l, r]中与b互质的数的个数?这个玩意等于∑i|bu(i)*(r/i).然后发现可以把b分解质因数.而且只留下u不为0的.于是就能出奇迹辣好厉害ovo
比较神奇的数学题.首先你得听说过一个东西叫Mertens函数.于是你可以找到一篇论文.然后你发现它是英文的.试图理解了很久没有成功. 然后终于有人良心贴出了一个blog.这回懂辣开心ovo 其实就是那一个公式:F(n) = ∑一堆约数 + ∑k=2nF([n/k]) 然后发现mu和phi的左边一堆都是可以O(1)算的辣.右边强行记搜可以做到O(n2/3)的辣. 然后手写个hash啥的就能跑得飞快的辣.
网没救啦.然后发现看电影居然看得无聊了.于是去愉快地刷题了ovo 来复习一下一个叫prufer序列的东西.它是用来做生成树计数的.考虑一棵有标号的树,每次把叶子中编号最大的一个节点的唯一一条边的另一边扔进序列尾部,然后把它扯了,直到只剩俩点.然后发现这个序列对于一棵树是唯一的,且一个序列对应唯一的树.且这个序列的取值全都是1到n的数,无相互限制.这也是为啥完全图的生成树个数是nn-2. 然后这个题是给定度数嘛,于是就是对于每个点要求在prufer序列中出现次数一定.那也很好做的啦. 然后要注意的是有一堆无解的情况要先判断一下.然后听说写c++要小心暴long long.我强行python无压力啦ovo
比较好想的dfs容斥，然后二分答案。 就只用dfs不超过sqrt(n)的素数的平方和。
idy又开坑辣。 mobius反演题么么哒。强行sqrt(n)的询问。 于是推一下式子。 answer = ∑i∑j1 (gcd(i, j) = 1) = ∑<sub>p</sub>∑<sub>g</sub>u(g) * (n/(p*g)) * (m/(p*g)) 然后把p和g合起来设为v。 h(v) = ∑ u(v) (v = x/p) 然后发现h(v)函数是很好推的。 h(px) = (x % p == 0) ? (u(x)) : (u(x) - h(x)) 然后就搞定啦orz.
上课讲的神题。构造公式。本来用HTML写了一堆公式的。然后天杀的网就断了要我重新开然后就没了。很想骂人。那就不写了呗，自行翻课件或者yy。
<div class="post_brief"><p> 每日一水。不过这题还比较有意思。最初没看清题，觉得没法数总三角形个数。</p> 同色=总-不同色。对于一个不同色，会有两个顶点的两边颜色不同。直接按照顶点统计一下不同色的边组数，然后减一下就完了。 说好的糖果呢。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1009; int n, m, t, c, w[maxn]; int main() { #ifndef ONLINE_JUDGE //freopen(“in.txt”, “r”, stdin); #endif scanf("%d%d", &n, &m); memset(w, 0, sizeof(w)); t = n * (n - 1) * (n - 2) / 6; for (int i = 0; i < m; ++ i) { int u, v; scanf("%d%d", &u, &v); ++ w[u]; ++ w[v]; } c = 0; for (int i = 1; i <= n; ++ i) c += w[i] * (n - w[i] - 1); c >>= 1; printf("%d\n", t - c); }
<div class="post_brief"><p> 一道burnside，做了几次之后感觉比较经典了。然后发现网上居然没有题解。</p> 枚举正整数拆分，既每个质换的长度。然后枚举gcd算每类置换的贡献。再用错排公式来算每类置换的数量。然后求和。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) const int maxn = 63; int n, m, mod, ans, g[maxn][maxn]; int sq[maxn], tq, fac[maxn], finv[maxn], vinv[maxn]; int modPow(int a, int x) { int s(1); for (; x; x >>= 1, a = _l a * a % mod) if (x & 1) s = _l s * a % mod; return s; }...
<div class="post_brief"><p> 推了半天，发现还是得sqrt，过不到啊。</p> 然后发现与经典的问题相比，就是n=n。然后这不是做过的那个LCM sum的前缀和就完了嘛。傻了。 然后第一次MLE是因为明明压了8位，还是开了30长的数组。第二次WA是因为高精输出的时候%08d写成了%8d。是不是明天又要逗极而死了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #define _l (long long int) const int maxlen = 7; const dint base = 1e8; struct BigInt { dint dig[maxlen], len; BigInt() { len = 0; } void set(dint x) { dig[0] = x; len = 1; while (dig[len - 1] >= base) { dig[len] = dig[len - 1] / base; dig[len - 1] %= base; ++ len; } } void copy(const BigInt& x) { len = x....
<div class="post_brief"><p> 首先是burnside，对于旋转x下都要当作一个置换，所以总共有n个。然后第i个的不动点数量等于n<sup>gcd(n,i)</sup>，然后统计一下个数是phi(gcd(n,i))个。</p> 然后发现要用奇奇怪怪的东西来求phi。我用的方法是分解质因数然后DFS，跑得飞快。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) const int maxn = 50009; int n, mod; int tp, pn[maxn], phi[maxn]; bool pr[maxn]; void pre() { memset(pr, 0, sizeof(pr)); tp = 0; phi[1] = 1; for (int i = 2; i < maxn; ++ i) { if (!pr[i]) { pn[tp ++] = i; phi[i] = i - 1; } for (int j = 0; j < tp && i * pn[j] < maxn; ++ j) { pr[i * pn[j]] = 1; if (i % pn[j] == 0) { phi[i * pn[j]] = phi[i] * pn[j]; break; } else phi[i * pn[j]] = phi[i] * phi[pn[j]]; } } }...