首页 > 代码库 > 湘潭 A simple problem

湘潭 A simple problem

2024-07-07 13:17:41   231人阅读

A simple problem

Accepted : 30   Submit : 303
Time Limit : 15000 MS   Memory Limit : 655360 KB

 

Problem Description

There is a simple problem. Given a number N. you are going to calculate N%1+N%2+N%3+...+N%N.

Input

First line contains an integer T, there are T(1≤T≤50) cases. For each case T. The length N(1≤N≤1012).

Output

Output case number first, then the answer.

Sample Input

1
5

Sample Output

Case 1: 4

Source

daizhenyang

 

 1 import java.io.*;
 2 import java.awt.*;
 3 import java.math.BigInteger;
 4 import java.util.Scanner;
 5 
 6 public class Main {
 7 
 8     public static void main(String[] args) {
 9         Scanner cin = new Scanner(System.in);
10         int T = cin.nextInt();
11         for(int t=1;t<=T;t++)
12         {
13             long n =cin.nextLong();
14             BigInteger m =solve(n);
15             System.out.println("Case "+t+": "+m);
16         }
17     }
18     static BigInteger solve(long n)
19     {
20         BigInteger sum = BigInteger.ZERO;
21         long k = (long)Math.sqrt(n*1.0);
22         if(k*k!=n) k++;
23         long y = n;
24         long a1,d=1,x;
25         while(y>=k+1)
26         {
27             a1=n%y;
28             x=(y-a1+d)/(d+1);
29             sum = sum.add(get(a1,x,d));
30             y=y-x;
31             d++;
32         }
33         for(int i=2;i<=y;i++)
34         {
35             sum=sum.add(BigInteger.valueOf(n%i));
36         }
37         return sum;
38     }
39     static BigInteger get(long a1,long x,long d)
40     {
41         BigInteger sum = BigInteger.ZERO;
42         BigInteger a = BigInteger.valueOf(a1);
43         BigInteger cur = BigInteger.valueOf(d);
44         BigInteger an = a.add(BigInteger.valueOf(x-1).multiply(cur));
45         
46         an = an.add(a);
47         sum = an.multiply(BigInteger.valueOf(x));
48         sum = sum.divide(BigInteger.valueOf(2));
49         return sum;
50     }
51 }

 

 

 


联系
我们