SICAU-OJ： A|B

A|B

题意：

给出一个整数n(1<=n<=10¹⁰⁰)，求Σd（d满足d可以整除n），同时保证不存在x^2有x^2可以整除n。

另外，n的质因子满足小于等于1000。

题解：

这题是我第一道用python做的题...毕竟大数C写起来还是挺麻烦的。

根据唯一分解定理我们知道n=p1^a1*p2^a2*....*pn^an，再来看条件，我们知道这里的p1...pn都是小于等于1000的。

另外，由不存在x^2可以整除n可知：a1=a2=...=an=1。

倘若at>1，那么一定有一个x^2是n的因子。毕竟n是由这些数给乘起来的。

最后我们统计答案时，计算(p1+1)*(p2+1)*....*(pn+1)就行了，可以十分方便地计算出所有的情况。

代码如下：

prim=[]

vis=[]

for i in range(1000):vis.append(0)

for i in range(2,1000):

    if(not vis[i]):

        prim.append(i)

        for j in range(i*i,1000,i):

            vis[j]=1;

t=int(input())

while(t):

    t-=1

    need=[]

    sum=1

    n=int(input())

    l = len(prim)

    for i in range(l):

        if(n%prim[i]==0):

            need.append(prim[i])

    l=len(need)

    for i in range(l):

        sum*=(need[i]+1)

    print(sum)

巴特西

SICAU-OJ： A|B

最新文章

热门文章