HDU 5646 DZY 파 티 션 사랑(수학)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=5646
DZY Loves Partition
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 887    Accepted Submission(s): 327
Problem Description
DZY loves partitioning numbers. He wants to know whether it is possible to partition 
n  into the sum of exactly 
k  distinct positive integers.
After some thinking he finds this problem is Too Simple. So he decides to maximize the product of these 
k  numbers. Can you help him?
The answer may be large. Please output it modulo 
109+7 .
 
Input
First line contains 
t  denoting the number of testcases.
t  testcases follow. Each testcase contains two positive integers 
n,k  in a line.
(
1≤t≤50,2≤n,k≤109 )
Output
For each testcase, if such partition does not exist, please output 
−1 . Otherwise output the maximum product mudulo 
109+7 .
Sample Input

   
   
   
   

    
    
    
    4
3 4
3 2
9 3
666666 2
   
   
   
   

Sample Output

   
   
   
   

    
    
    
    -1
2
24
110888111

   
   
   
   
   
   
   
   


   
   
   
   

제목:n 개 수 를 k 개의 서로 다른 정수 로 나 누 어 이 n 개의 정수 의 최대 곱 하기
방법:sum(1,k)은 k 개 수 에 추 가 된 최소 값 입 니 다.n 이 이 수 보다 작 으 면 n 은 k 개 수로 나 눌 수 없습니다.n>sum(1,k)은 k 개의 연속 적 인 수 나 차이 가 2 인 연속 상승 수열 이 존재 합 니 다. n=n-sum(1,k) , c=n/k,d=n%k,만약 d!=0 은 차이 가 2 수 이기 때문에 이때 수열 을 두 부분 으로 나 누고 앞부분 은 연속 적 인 수열 이 며 뒷부분 은 차이 가 2 인 수열 로 나 누 어 그들 을 누적 곱 한다.

#include <bits/stdc++.h>
#define Mod 1000000007
using namespace std;

int main()
{
    int T;
    long long n, k;
    scanf("%d",&T);
    while(T-- && scanf("%lld %lld",&n,&k))
    {
        long long sum = (k + 1) * k / 2;
        if(sum > n)
        {
            printf("-1
");
            continue;
        }
        n -= sum;
        long long c = n / k;
        long long d = n % k;
        long long ans = 1;
        for(int i=c+1; i<=k+c; i++)
        {
            if(i <= k-d+c)  ans = (ans * i) % Mod;
            else   ans = (ans * (i+1)) % Mod;
        }
        printf("%lld
", ans%Mod);
    }
    return 0;
}