❤BZOJ 2705: [SDOI2012]Longge的问题

我会带着你远行 2022-07-29 08:59 148阅读 0赞

## 2705: \[SDOI2012\]Longge的问题 ##

Time Limit: 3 Sec Memory Limit: 128 MB  
Submit: 2007 Solved: 1247  
\[[Submit][]\]\[[Status][]\]\[[Discuss][]\]

## Description ##

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

## Input ##

一个整数，为N。

## Output ##

一个整数，为所求的答案。

## Sample Input ##

6

## Sample Output ##

15

## HINT ##

【数据范围】  
  
对于60%的数据，0<N<=2^16。  
  
对于100%的数据，0<N<=2^32。

#include<iostream>
    #include<cstdio>
    #include<cmath> 
    using namespace std;
    long long n,ans;
    long long phi(long long x)
    {
        long long ans=x,m=x;
        for (long long i=2;i<=(long long)sqrt(x);i++)
          if (m%i==0)
           {
             ans=ans/i*(i-1);
             while (m%i==0) m/=i; 
           }
        if (m>1) ans=ans/m*(m-1);
        return ans;
    }
    int main()
    {
       cin>>n;
       for (long long i=1;i<=sqrt(n);i++)
          if (n%i==0)
           {
             ans+=phi(i)*(n/i);
             if (i!=n/i) ans+=phi(n/i)*i;
           }
        cout<<ans<<endl;
    }

[Submit]: http://www.lydsy.com/JudgeOnline/submitpage.php?id=2705
[Status]: http://www.lydsy.com/JudgeOnline/problemstatus.php?id=2705
[Discuss]: http://www.lydsy.com/JudgeOnline/bbs.php?id=2705

发表评论取消回复

表情：

评论列表（有 0 条评论，148人围观）

还没有评论，来说两句吧...

相关阅读

相关 @bzoj - 3130@ [Sdoi2013]费用流

目录 @description@ @solution@ @accepted code@ @details@ --------------------

小咪咪/ 2023年06月01日 13:59/ 0 赞/ 2 阅读

相关 ❤BZOJ 2705: [SDOI2012]Longge的问题

2705: \[SDOI2012\]Longge的问题 Time Limit: 3 Sec Memory Limit: 128 MB Submit: 2007 Sol

我会带着你远行/ 2022年07月29日 08:59/ 0 赞/ 149 阅读

相关 [bzoj1951][SDOI2010]古代猪文

题目描述: 计算G^(Sigma(C(n,i)) % P，其中 i | n 题目解答：为叙述方便起见，我们令sigma()为W 显然W是一个非常大的数，如

清疚/ 2022年07月11日 13:21/ 0 赞/ 181 阅读

相关 bzoj 1878: [SDOI2009]HH的项链

传送门：[点我][Link 1] Description HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一

秒速五厘米/ 2022年05月15日 23:59/ 0 赞/ 181 阅读

相关 BZOJ3012 : [Usaco2012 Dec]First!

建立Trie，那么成为答案的串必须满足其终止节点到根路径上没有其它点。对于Trie上每个节点维护一个bitset，表示哪些字符必须在哪些字符之前。每到达一个可能成为答案

深碍√TFBOYSˉ_/ 2022年04月10日 11:24/ 0 赞/ 172 阅读

相关 BZOJ2242[SDOI2011]计算器——exgcd+BSGS

题目描述你被要求设计一个计算器完成以下三项任务： 1、给定y,z,p,计算Y^Z Mod P 的值； 2、给定y,z,p，计算满足xy≡ Z ( mod P )的最

约定不等于承诺〃/ 2022年01月05日 15:15/ 0 赞/ 220 阅读

相关【BZOJ1227】[SDOI2009]虔诚的墓主人

E. 虔诚的墓主人题目描述小W 是一片新造公墓的管理人。公墓可以看成一块N×M 的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块还没有归属的墓地。当地的居

喜欢ヅ旅行/ 2021年11月09日 09:10/ 0 赞/ 264 阅读

相关 [bzoj2242] [SDOI2011]计算器

\570. \[bzoj2242\] \[SDOI2011\]计算器题目描述你被要求设计一个计算器完成以下三项任务： 1、给定y,z,p,计算Y^Z Mod

清疚/ 2021年10月29日 07:18/ 0 赞/ 278 阅读

相关 bzoj 1227: [SDOI2009]虔诚的墓主人

Description 小W 是一片新造公墓的管理人。公墓可以看成一块N×M 的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块还没有归属的墓地。当地的居民都是非常虔

不念不忘少年蓝@/ 2021年10月01日 02:04/ 0 赞/ 260 阅读

相关 BZOJ2242：[SDOI2011]计算器——题解

[https://www.lydsy.com/JudgeOnline/problem.php?id=2242][https_www.lydsy.com_JudgeOnline_

灰太狼/ 2021年09月20日 09:36/ 0 赞/ 275 阅读