[BZOJ] [Jsoi2013]丢番图

题目分析

Description

丢番图是亚历山大时期埃及著名的数学家。他是最早研究整数系数不定方程的数学家之一。
为了纪念他,这些方程一般被称作丢番图方程。最著名的丢番图方程之一是x^N+y^n=z^N。费马提出,对于N>2,x,y,z没有正整数解。这被称为“费马大定理”,它的证明直到最近才被安德鲁·怀尔斯(AndrewWiles)证明。
考虑如下的丢番图方程:
1/x+1/y=1/n(x,y,n属于N+) (1)
小G对下面这个问题十分感兴趣:对于一个给定的正整数n,有多少种本质不同的解满足方程(1)?
例如n=4,有三种本质不同(x≤y)的解:
1/5+1/20=1/4
1/6+1/12=1/4
1/8+1/8=1/4
显然,对于更大的n,没有意义去列举所有本质不同的解。你能否帮助小G快速地求出对于
给定n,满足方程(1)的本质不同的解的个数?

Input

一行,仅一个整数n(1<=N<=10^14)

Output

一行,输出对于给定整数n,满足方程(1)的本质不同的解的个数。

Sample Input

4

Sample Output

3

题目分析

题目本质:

现在来化简一下式子:

于是直接求出 的约数个数即可
根据约数个数公式,可以把n分解质因数,质因子的幂次*2即为中的幂次,再+1乘起来即可得到的约数个数。
并且题目中要求本质不同,所以约数个数/2 算了两次,应该减掉。
即可得到答案。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long n;
long long ans=1;
int main()
{
    scanf("%lld",&n);
    for(long long i=2;i*i<=n;i++)
        if(n%i==0)
        {
            int tmp=0;
            while(n%i==0) tmp++,n/=i;
            ans=ans*(2*tmp+1);
        }
    if(n>1) ans*=3;
    if(ans%2==1) ans++; 
    printf("%lld",ans>>1);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注