【JZOJ 3858】【NOIP2014八校联考第3场第2试10.5】挖掘机技术哪家强

题目大意:

给定一个数 \(n\),对于每个 \(n\),都有能整除它的数 \(x\),我们最后要输出的结果是每个 \(x\) 的“难挖指数”的和。

正文:

举一个例子,当 \(x=5\) 时, 有和它互质的数 \(y \in \{1,2,3,4\}\)。

此时我引出一条定理,当 \(x\) 与 \(y\) 互质时,\(x\) 和 \((x-y)\) 也互质。那我们给"\(y\)"和"\((x-y)\)"分到一组,分别是 \(\{1,4\},\{2,3\}\)。

很容易发现,每组的和是 \(x\),有 \(\dfrac{\varphi (x)}{2}\) 组(注意当\(x=1\)或\(2\)时,\(\varphi(x)=1\),需要特判),那\(x\)的难挖指数求出来了。

代码:

ll Ans(ll n)
{
    if(n == 1) 
    {
        return 1;
    }
    ll sum = n, n_ = n;
    for (int i = 1; i <= cnt; i++)
    {
        if(n % prime[i] == 0 ) 
        {
            sum = sum * (prime[i] - 1) / prime[i];
            for (; n % prime[i] == 0; n /= prime[i]);
        }
        if(n == 1) break;
    }
    if(n > 1)
    {
        sum = sum * (n - 1) / n;
    }
    return sum * n_ / 2;
}

int main()
{
    n = 100000;
    init();
    for (scanf ("%lld", &t); t--;)
    {
        ans = 0;
        scanf ("%lld", &n);
        for (ll i = 1; i * i <= n; i++)
        {
            if(n % i == 0)
            {
                ans += Ans(i);
                if (i * i != n) ans += Ans(n / i);
            }
        }
        printf("%lld", ans);
        puts("");
    }
    return 0;
}
上一篇:208. 实现 Trie (前缀树)


下一篇:noip2014联合权值