【8.5】Code Source - 【GCD】【Sequence Median】【Maximum Number of Concatenated Edges】

#871. GCD

题意：给定 $1\le a<m\le 10^{10}$ ,计算 ${\sum }_{x=0}^{m-1}[\gcd (a,m)=\gcd (a+x,m)]$ .

题解：(Interval coprime) 代码源每日一题 Div1 GCD

思路：推一下式子：

容易知道 $k=\gcd (a,m)$ 一定是 $m$ 的因子.我们先计算出 $a+x$ is within the range $k$ The left and right boundaries of multiples of ,The multiple range is $[l,r]=[\lceil \frac{a}{k}\rceil ,\lfloor \frac{a+m-1}{k}\rfloor ]$ .那么 ${\sum }_{x=0}^{m-1}[\gcd (a,m)=\gcd (a+x,m)]={\sum }_{i=l}^r[\gcd (i,\frac{m}{k})=1]$ ,那么问题转化为求 $l\sim r$ 中有多少个数与 $\frac{m}{k}$ 互质.

A classic problem is asking $1\sim n$ 有多少个数与 $m$ 互质,方法为：对 $m$ 分解质因子,Then the binary enumeration is inclusive and exclusive,时间复杂度 $O(\sqrt{n}+2^{11})$ ,这里的 $11$ 是指 $10^{10}$ The number inside has the most $11$ 个质因子.

总结了一些关于 $\gcd$ 的性质：

$\gcd (a,b)=\gcd (a,a+b)$ ,The prefix of the sequence and the sequence or the difference sequence $\gcd$ 相等
$\gcd (k\times a,k\times b)=k\times \gcd (a,b)$
$\gcd (a,b)=p\times \gcd (\frac{a}{p},\frac{b}{p})$ ,要保证 $p$ 是 $a,b$ 的因子
$\gcd (a^k,b^k)={\gcd }^k(a,b)$
$c|a\times b\Rightarrow \frac{c}{\gcd (b,c)}|a$

模板：

LL cal(LL n, LL m){
     // numbers of i in 1 ~ n : gcd(i, m) == 1
    vector<LL> vec;
    for(LL i = 2; i * i <= m; i ++ ){
    
        if(m % i == 0){
    
            while(m % i == 0) m /= i;
            vec.pb(i);
        }
    }
    if(m > 1) vec.pb(m);
    LL res = 0;
    for(int bit = 1; bit < 1 << vec.size(); bit ++ ){
    
        LL mul = 1;
        rep(i, 0, (int)vec.size() - 1) if(bit >> i & 1) mul *= vec[i];
        if(__builtin_popcount(bit) & 1) res += n / mul;
        else res -= n / mul;
    }
    return n - res;
}

AC代码：http://oj.daimayuan.top/submission/321288

#877. Sequence median

题意：给定正整数 $N$ , 求出 $1\sim N-1$ 中所有与 $N$ A sequence of relatively prime numbers 的中位数.

我们定义 : 一个长度为 $K$ The median of the sequence is the first in the sequence $\lfloor \frac{K+1}{2}\rfloor$ 大的数字. and two positive integers $a$ 与 $b$ Coprime if and only if $\gcd (a,b)=1$ .

思路：Play the table to find the rules.证明的话： $\gcd (i,x)=\gcd (x-i,x)$ ,Probably this is the formula.

AC代码：http://oj.daimayuan.top/submission/322050

#916. Maximum number of edges

题意：$1\le n\le 10^5$

题解：(树状数组/DP) 代码源每日一题 Maximum number of edges

思路：树状数组优化 DP .

We enumerate by subscript $a$ 里的元素,去枚举 $b$ corresponding element.我们先定义 $dp(i,j)$ 表示 $a$ 前 $i$ 个元素和 $b$ 前 $j$ Maximum match of elements,转移方程为 $dp(i,j)={\max }_{1\le i^{\prime }<i,1\le j^{\prime }<j}dp(i^{\prime },j^{\prime })+1$ .

It can be found that this is a two-dimensional partial order,The first dimension can be optimized.for and currently enumerated $i$ 对应的 $j$ ,转移方程为 $dp(j)=\max (d{p}^{\prime }(j),{\max }_{k=1}^{j-1}d{p}^{\prime }(k)+1)$ ,Just use the tree array to maintain the prefix value of the second dimension.

AC代码：http://oj.daimayuan.top/submission/322797