题目链接：bzoj2705 题目大意： 求 ∑ni=1gcd(i,n) \sum_{i=1}^{n}gcd(i,n)， 0<N≤232 0<N≤2^{32}。 题解： 数论，欧拉函数 设 d d为nn的约数，有 i=i′×d i=i'\times d 于是式子就可以写成 ∑d|nd∑1≤i′d≤n,(i′d,n)=d1 \sum_{d|n}d\sum_{1≤i'd≤n,(i'

题目链接： bzoj2726 洛谷2365 洛咕上好像 O ( n 2 ) O(n^2) O(n2)能过……还没有负数的情况…… 如果没有负数，就直接大莉上斜率优化就珂以了qwq 转移方程是 d p [ i ] = d p [ j ] + s u m T [ i ] ∗ ( c [ i ] − c [ j ] ) + S ∗ ( c [ n ] − c [ j ] ) dp[i]=dp[j]+s

Description Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。 Input 一个整数，为N。 Output 一个整数，为所求的答案。 ∑i=1ngcd(i,n)=∑i=1n∑d∣gcd(i,n)φ(d)=∑i=1n∑d∣i∧d∣nφ(d)=∑d∣nφ(d)∗dn \

Description Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。 Input 一个整数，为N。 Output 一个整数，为所求的答案。 Sample Input 6 Sample Output 15 HINT 【数据范围】 对于60%的数据，0< N<=2^16。