[NOIP模拟赛]不完美值

题目描述 如果一个数等于它的真因子之和，这样的数称为完数。如28=1+2+4+7+14，所以28为完数。我们可以定义不完美值为一个数与它的所有真因子之和的差的绝对值。令F(N)为不完美值，则有： F(6)=|6-1-2-3|=0, F(11)=|11-1|=10, F(24)=|24-1-2-3-4-6-8-12|=|-12|=12

写一个程序，对于整数A,B,计算从A到B的所有数的不完美值之和：F(A)+F(A+1)+F(A+2)+……+F(B)

输入格式

第一行包含两个整数A,B(1<=A<=B<=10^7)

输出格式

一个整数，即答案。

输入样例 1 9 输出样例

21

题解：

设f[i]为i的所有因子之和，则其真因子之和即为f[i]-i。 可以将i分解质因数，设i=p1^k1*p2^k2*……pn^kn，那么f[i]=(1+p1+p1^2+……p1^k1)*(1+p2+p2^2+……p2^k2)*…*(1+pn+pn^2+……pn^kn)， 于是可以采用类似筛质数的方法求出每个数的f[i]值。

#include<cstdio> typedef long long LL; const int N=1e7+10; int A, B; LL sum, ans[N]; int Abs( int x ) { return x<0 ? (-x) : x; } int main() { scanf( "%d%d", &A, &B ); ans[1]=1; for( int i=2; i<=B; i++ ) if( !ans[i] ) { for(int j=2;j*i<=B;j++) { int t=j*i, w=1, c=i; while( !(t%i) ){ t/=i; w+=c; c*=i; } if( !ans[j*i] ) ans[j*i]=1; ans[j*i]*=w; } ans[i]=1+i; } for( int i=A; i<=B; i++ ) sum+=Abs( ans[i]-i-i ); printf( "%I64d\n", sum ); return 0; }