首页 > 专题系列 > Java解POJ > POJ 2757 Beautiful Numbers [解题报告] Java
2013
11-11

POJ 2757 Beautiful Numbers [解题报告] Java

Beautiful Numbers

问题描述 :

Now that you believe Jiajia & Wind’s cute daughter, Autumn, is a genius. It’s not surprising that such a clever little girl would have no interest on simple additions very soon. This time, she turned to divisions, since they’re more fun. For example, she found herself that if the sum of digits of a decimal number is a multiple of 3, then the decimal number itself is also a multiple of 3. The argument is still true if she replaces the number 3 with 9.

Inspired by these, Autumn invented a special kind of number, called ‘Beautiful Numbers’. A number k is said to be Beautiful in base b, if the sum of digits of k in base b is a multiple of b.

Autumn knows how to calculate the sum of first n beautiful numbers in base b, can you?

输入:

The input contains a single test case with two lines. The first line is a single integer n(n < 101001), the second line is a single integer b(1 < b < 1001).

输出:

The output contains a single integer, the sum of first n beautiful numbers in base b. You should output the sum in decimal, not in base b.

样例输入:

2
3

样例输出:

12

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
public class Main 
{
 public static void main(String args[]) throws Exception {
	
	Scanner cin=new Scanner(System.in);
	BigInteger n;
	long b;
	while(cin.hasNext())
	{
		n=cin.nextBigInteger();
		b=cin.nextLong();
		if(n.compareTo(BigInteger.ZERO)<=0)
		{
			System.out.println("0");
			continue;
		}
		BigInteger ans;
		ans=n.multiply(n.add(BigInteger.ONE)).divide(BigInteger.valueOf(2));
		ans=ans.multiply(BigInteger.valueOf(b));
		//how many [0..b-1]
		BigInteger cnt=n.divide(BigInteger.valueOf(b));
		ans=ans.add(BigInteger.valueOf(b*(b-1)/2).multiply(cnt));
		cnt=cnt.multiply(BigInteger.valueOf(b));
		while(cnt.compareTo(n)<=0)
		{
			BigInteger tmp=BigInteger.ZERO,tsum=cnt;
			while(tsum.compareTo(BigInteger.ZERO)>0)
			{
				tmp=tmp.add(tsum.mod(BigInteger.valueOf(b)));
				tsum=tsum.divide(BigInteger.valueOf(b));
			}
             tmp=(BigInteger.valueOf(b).subtract(tmp.mod(BigInteger.valueOf(b)))).mod(BigInteger.valueOf(b));
			cnt=cnt.add(BigInteger.ONE);
			ans=ans.add(tmp);
		}
		System.out.println(ans);
	}
  }
}

  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测