hdu1299Diophantus of Alexandria

   1/x+1/y = 1/n 设y = n + k;==>1/x + 1/(n+k)=1/n;==>x = n^2/k + n;因为x为整数,k就是n^2的约数。————题解
改成高效的素数筛也对了,还是挺开心的^_^ 这下子知道了数论的题真是_(:зゝ∠)_出来的 呵呵~

Problem Description
Diophantus of Alexandria was an egypt mathematician living in Alexandria. He was one of the first mathematicians to study equations where variables were restricted to integral values. In honor of him, these equations are commonly called diophantine equations. One of the most famous diophantine equation is x^n + y^n = z^n. Fermat suggested that for n > 2, there are no solutions with positive integral values for x, y and z. A proof of this theorem (called Fermat's last theorem) was found only recently by Andrew Wiles.
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e7+9;
long long prime[N/10]={0},num_prime=0;
bool isnotprime[N];
int fac[100000];
void init()
{
     memset(isnotprime,false,sizeof(isnotprime));
     isnotprime[0]=true,isnotprime[1]=true;
     for(long long i=2;i<N;i++)
     {
          if(!isnotprime[i])
               prime[num_prime++]=i;
          for(long long j=0;j<num_prime&&i*prime[j]<N;j++)
          {
               isnotprime[i*prime[j]]=true;
               if(!(i%prime[j]))break;
          }
     }
}
long long get(int x)
{
     int tot=0;
     memset(fac,0,sizeof(fac));
     for(int i=0;i<num_prime&&prime[i]*prime[i]<=x;i++)
     {
          if(x%prime[i]==0)
          {
               while(x%prime[i]==0)
                    fac[tot]++,x/=prime[i];
               tot++;
          }
     }
     if(x>1) fac[tot++]=1;
     long long ans=1;
     for(int i=0;i<tot;i++)
          ans=ans*(2*fac[i]+1);
     return ans;
}
int main()
{
       // freopen("cin.txt","r",stdin);
        init();
    int t,cas=1;
    scanf("%d",&t);
    while(t--){
        long long n;
        scanf("%lld",&n);
        printf("Scenario #%d:\n%I64d\n\n",cas++,(get(n)+1)/2);
    }
    return 0;
}



Consider the following diophantine equation:

<center> 1 / x + 1 / y = 1 / n where x, y, n ∈ N+ (1) </center>

Diophantus is interested in the following question: for a given n, how many distinct solutions (i. e., solutions satisfying x ≤ y) does equation (1) have? For example, for n = 4, there are exactly three distinct solutions:

<center> 1 / 5 + 1 / 20 = 1 / 4
1 / 6 + 1 / 12 = 1 / 4
1 / 8 + 1 / 8 = 1 / 4 </center>


Clearly, enumerating these solutions can become tedious for bigger values of n. Can you help Diophantus compute the number of distinct solutions for big values of n quickly?
 

Input
The first line contains the number of scenarios. Each scenario consists of one line containing a single number n (1 ≤ n ≤ 10^9).
 

Output
The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Next, print a single line with the number of distinct solutions of equation (1) for the given value of n. Terminate each scenario with a blank line.
 

Sample Input
2 4 1260
 

Sample Output
Scenario #1: 3 Scenario #2: 113
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-11 11:29
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 12:05
俺不中了,BOSS遇到了一个hr,我觉得我咨询的问题都很正常吧,然后直接就被拒绝了???
恶龙战士:你问的太多了,要不就整理成一段话直接问他,一个一个问不太好
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务