数学题目合集

翻转

性质：如果翻转的区间所有数对个数为偶，则整个逆序对个数奇偶性不变；否则改变。

证明：首先翻转区间外的逆序对个数不会变化，翻转区间与翻转区间外的逆序对个数也不会变化。

假设翻转前翻转区间内有 \(cnt\) 个逆序对，则翻转后有 \(len\times (len-1)/2-cnt\) 个逆序对，差为 \(len\times(len-1)/2-2\times cnt\)，奇偶性由 \(len\times (len-1)/2\) 决定，即区间所有数对个数。

HDU2588

求 \(1\sim n\) 中与 \(n\) 的 \(gcd\ge m\) 的数的个数。\(n:1e9\)。

\(gcd(x,n)=g\ge m\)，设 \(x=ga,n=gb\)，\((a,b)=1\)。

我们枚举 \(g\)，然后因为 \(x=ga\)，所以 \(a\) 的个数就是 \(x\) 的个数。而 \(a\) 的限制条件是 \((a,b)=1\)，也就是 \((a,n/g)=1\)，因为 \(a=x/g,x\le n\) 所以 \(a\le n/g\)。

因此 \(a\) 的个数就是 \(\varphi(n/g)\)。

\(O(\sqrt n)\) 枚举所有 \(\ge m\) 的 \(n\) 的因子，对它们的 \(\varphi\) 求和即可。求欧拉函数直接 \(O(\sqrt x)\) 求。