n%i之和

  • Post author:
  • Post category:其他




题目:





http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1168






题意:

给定一个n,注意这里n小于10^12,求



分析:早些时候就做过一道题,在这里:




http://blog.csdn.net/acdreamers/article/details/8809517



由于当时这题数据小,直接计算步长更方便,但是对于本题由于10^12就不合适了,那么我们就采用第二种方法,现


在我就分别


简略说说这两种方法,其实大体思路差不多,只是处理不一样。



首先是不可能直接枚举的,那么我们先把

写成

,所以问题变为求:



由于

在一定范围内是保持不变的,所以我们接下来可以把时间复杂度降到



现在我们简略模拟一下:比如n=30,那么我们可以划分等价类:






可以看出,我们第一个和最后一个组合,第二个和倒数第二个组合,等等,如此进行下去,注意如果是奇数项,中间


的那个只


被加一次,这样我们只需要枚举到

就行了。这个方法很好,其实还有一个相对还算可以方法,那么就是


记录每个等价类的


首元素和尾元素,每次跳一段长度,这样对于10^9数据完全没有问题。



本题由于数据很大,所以用Java大数:

import java.math.BigInteger;
import java.util.Scanner;
import java.math.*;

public class Main
{
	   public static BigInteger Solve(long n)
	   {
		   BigInteger ans=BigInteger.ZERO;
		   long i,t=(long) Math.sqrt(n*1.0);
		   for(i=1L;i<=t;i++)
		   {
			   BigInteger a=BigInteger.valueOf(n/i+n/(i+1)+1); 
			   BigInteger b=BigInteger.valueOf(n/i-n/(i+1));
			   BigInteger temp=BigInteger.ZERO;
			   if(i!=(n/i))
			       temp= (a.multiply(b)).divide(BigInteger.valueOf(2));
			   BigInteger c=BigInteger.valueOf(n/i);
			   BigInteger ret=c.add(temp);
			   ret=ret.multiply(BigInteger.valueOf(i));
			   ans=ans.add(ret);
		   }
		   return ans;
	   }
	
	   public static void main(String[] args)
	   {
		      Scanner cin = new Scanner(System.in);
		      while(cin.hasNextLong())
		      {
		    	   long n=cin.nextLong();
		    	   BigInteger x=BigInteger.valueOf(n);
		    	   System.out.println((x.multiply(x)).subtract(Solve(n)));
		      }
	   }
}



版权声明:本文为ACdreamers原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。