数论中的基本算法 POJ 1845 SPOJ DIVSUM

扩展欧几里得 求逆元（只要a与b互素，那么就有逆元）

#include<cstdio>using namespace std;int sum[500100];int main(){    int T,t,i,j,n;    scanf("%d",&T);    for(i=1;i<=500000;i++){        for(j=2;i*j<=500000;j++){//若j从1开始则会算上本身            sum[i*j]+=i;        }    }    for(t=1;t<=T;t++){        scanf("%d",&n);        printf("%d\n",sum[n]);    }}