数论中的基本算法POJ 1845SPOJ DIVSUM扩展欧几里得 求逆元（只要a与b互素，那么就有逆元）#includecstdious
数论中的基本算法 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]); }}