链接&＃xff1a;https://www.nowcoder.com/acm/contest/82/A
来源&＃xff1a;牛客网

备注:

对于100%的数据&＃xff0c;t <&＃61; 500 , 1 <&＃61; n <&＃61; 1000000000000000000

思路&＃xff1a; 约数定理

约数定理&＃xff1a;n可以分解质因数&＃xff1a;n&＃61;p1^a1×p2^a2×p3^a3*…*pk^ak,
由约数定义可知p1^a1的约数有:p1^0, p1^1, p1^2......p1^a1 &＃xff0c;共&＃xff08;a1&＃43;1&＃xff09;个;同理p2^a2的约数有&＃xff08;a2&＃43;1&＃xff09;个......pk^ak的约数有&＃xff08;ak&＃43;1&＃xff09;个。

故根据乘法原理&＃xff1a;n的约数的个数就是(a1&＃43;1)(a2&＃43;1)(a3&＃43;1)…(ak&＃43;1)。

约数和定理&＃xff1a;

f(n)&＃61;(p1^0&＃43;p1^1&＃43;p1^2&＃43;…p1^a1)(p2^0&＃43;p2^1&＃43;p2^2&＃43;…p2^a2)…(pk^0&＃43;pk^1&＃43;pk^2&＃43;…pk^ak&＃xff09;

若n可以分解质因数&＃xff1a;n&＃61;p1^a1*p2^a2*p3^a3*…*pk^ak,
可知p1^a1的约数有:p1^0, p1^1, p1^2......p1^a1
实际上n的约数是在p1^a1、p2^a2、...、pk^ak每一个的约数中分别挑一个相乘得来&＃xff0c;
可知共有(a₁&＃43;1)(a₂&＃43;1)(a₃&＃43;1)…(ak&＃43;1)种挑法&＃xff0c;即约数的个数。
由乘法原理可知它们的和为

f(n)&＃61;(p1^0&＃43;p1^1&＃43;p1^2&＃43;…p1^a1)(p2^0&＃43;p2^1&＃43;p2^2&＃43;…p2^a2)…(pk^0&＃43;pk^1&＃43;pk^2&＃43;…pk^ak&＃xff09;

Code:

#include
using namespace std;
typedef long long LL;const int a[20]&＃61;{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int T;
LL n,ans;void DFS(int k,LL sum,LL ni,int m);
int main()
{ios::sync_with_stdio(false);cin>>T;while(T--){ans&＃61;1;cin>>n;DFS(0,1,1,15);cout<}void DFS(int k,LL sum,LL ni,int m)
{if(k>16) return;ans&＃61;max(ans,sum);for(int i&＃61;1;i<&＃61;m;&＃43;&＃43;i)if(ni<&＃61;n/a[k]){ni*&＃61;a[k];DFS(k&＃43;1,sum*(i&＃43;1),ni,i);}else break;
}