NYOJ 998 解题报告

POOPE

　　
Sum

　　时间限制： 1000 ms  |  内存限制： 65535 KB
　　难度： 3

　　描述　　 给你一个数N,使得在1~N之间能够找到x使得x满足gcd（ x ,  N  ） >= M，
　　求解gcd(x,N)的和

　　输入          多组测试数据   

每行输出两个数N，M（N,M不超int）          输出          输出sum          样例输入         

5 3

          样例输出          5　　这道题是一道关于欧拉函数的题目，但是由于时限的原因，使得这道题的算法必须尽可能的简化（我就是不断的TLE，渣渣啊 ）。咱们先把数学式子推导出来！假如gcd(x, N)=d，那么得到gcd(x/d, N/d)=1。所以。但是，我们不能直接就从M开始一直遍历到N，为什么呢？因为我已经TLE了！！！所以需要优化。这样想，gcd(x, N)的所有值一定能分成两组，一组是不超过sqrt(N)的值，另一组是大于sqrt(N)的值。所以只要从1遍历到sqrt(N)，将那些在M和sqrt(N)之间的项加到Sum里，那么大于sqrt(N)的那些项怎么办呢？其实在遍历时，假如d是n的一个因子，你们n/d也是n的一个因子（排除d*d=n的情形）。所以在遍历是通过(n/i)*phi(i)就把那些大于sqrt(N)的项加进来了。但是又要注意，n/i >= M，否则就把那些gcd小于M的项加进来了！！！
　　附上代码：

#include <stdio.h>
#include <math.h>
long long phi(long long n)
{
  long long i,sum=n,temp=n;
  for(i=2;i*i<=temp;i++)
  {
    if(n%i==0)
    {
      sum=sum/i*(i-1);
      while(n%i==0)
        n/=i;
    }
  }
  if(n>1)
    sum=sum/n*(n-1);
  return sum;
}
int main()
{
  long long m,n;
  while((scanf("%lld %lld",&n,&m))!=EOF)
  {
    long long sum=0,i;
    for(i=1;i<=(long long)sqrt(n);i++)
    {
      if(n%i==0)
      {
        if(i>=m)
          sum+=i*phi(n/i);
        if(i*i!=n&&n/i>=m)
          sum+=(n/i)*phi(i);
      }
    }
    printf("%lld\n",sum);
  }
  return 0;
}