首页 > 代码库 > 湘潭oj1203/邀请赛A题 数论+java大数

湘潭oj1203/邀请赛A题 数论+java大数

求 n%1+n%2+n%3+n%4+.........n%n=,n<=10^12次。

开始时盲目地找规律,结果一无所获。后来经学长点拨,天资愚钝,搞了半天才明白。


先上图:


对于该题,在求区间(根号n,n),由于n%i=n-i*x(这里x是从1枚举到根号n,每个k 对应n/(x+1)~n/x区间内,由于是等差数列(还是递减),直接用公式求和)。

哎(根号n,n)区间是被分割来求得,分成根号n次。

import java.io.*;
import java.util.Scanner;
import java.math.BigInteger;
public class Main{

	public static void main(String[] args) {
		int T;
	    Scanner in=new Scanner(System.in);
	    T=in.nextInt();
	    for(int ii=1;ii<=T;ii++)                
	    {
	          long n;                                    
	          BigInteger sum=new BigInteger("0");
	           n=in.nextLong();
	           long lasta=2*n;
	        for(long i=1;i*i<n;i++)
	        {
	        	 sum=sum.add(BigInteger.valueOf(n%i));
	        	 if((i+1)>=lasta){break;}              //边界判断
	        	  long b=n/i;
	              long a=n/(i+1)+1;
	              BigInteger temp1=BigInteger.valueOf(n);         //将一个 long型数据转为biginteger
	              temp1=temp1.multiply(BigInteger.valueOf((b-a+1)));   
	              BigInteger temp2=BigInteger.valueOf(b+a);
	              temp2=temp2.multiply(BigInteger.valueOf(i));    //*
	              temp2=temp2.multiply(BigInteger.valueOf(b-a+1));   
	              temp2=temp2.divide(BigInteger.valueOf(2));   //除以
	              temp1=temp1.subtract(temp2);                 // -
	            sum=sum.add(temp1);                             //+
	           lasta=a; 
	        }
	         System.out.println("Case "+ii+": "+sum);         //Java的println自动带换行。注意!
	    }

	}

}