首页 > 代码库 > 【数论】【枚举约数】【友好数】CODEVS 2632 非常好友

【数论】【枚举约数】【友好数】CODEVS 2632 非常好友

O(sqrt(n))枚举约数,根据定义暴力判断友好数。

 1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 int n; int limit; 5 int main() 6 { 7     scanf("%d",&n); 8     for(;;n++) 9       {10           limit=sqrt(n); int tot=1;11           if(limit*limit==n) tot+=limit;12           for(int i=2;i<limit;i++) if(n%i==0) tot+=(i+n/i);13           limit=sqrt(tot); int tot2=1;14           if(limit*limit==tot) tot2+=limit;15           for(int i=2;i<limit;i++) if(tot%i==0) tot2+=(i+tot/i);16           if(tot2==n)17           {18               printf("%d %d\n",n,tot);19               break;20           }21       }22     return 0;23 }

 

【数论】【枚举约数】【友好数】CODEVS 2632 非常好友