首页 > 其他 > 详细

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

时间:2020-02-02 21:40:39      阅读:86      评论:0      收藏:0      [点我收藏+]

题目大意:

给定一个数 \(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;
}

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

原文:https://www.cnblogs.com/GJY-JURUO/p/12253617.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!