#P2303. [SDOI2012] Longge 的问题
[SDOI2012] Longge 的问题
题目背景
Longge 的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。
题目描述
现在问题来了:给定一个整数 ,你需要求出 ,其中 表示 和 的最大公因数。
输入格式
输入只有一行一个整数,表示 。
输出格式
输出一行一个整数表示答案。
6
15
提示
数据规模与约定
- 对于 的数据,保证 。
- 对于 的数据,保证 。
Longge 的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。
现在问题来了:给定一个整数 n,你需要求出 i=1∑ngcd(i,n),其中 gcd(i,n) 表示 i 和 n 的最大公因数。
输入只有一行一个整数,表示 n。
输出一行一个整数表示答案。
6
15