XTUOJ 1187Candy

WCB某天买了非常多的糖果并把它们分成N份依次分别有123…,N个糖果。他想拿出其中的3份分给他的室友 为了不让室友们闹意见必须让这三份的糖果总数恰好能被三人均分。请问他一共有多少种不同的组合方案数

输入

有多组输入数据每组输入非负整数N(3≤N≤106),如果N0表示输入结束这个样例不需要处理。

输出

每组数据输出一个整数独占一行表示共有多少种方案由于可能会很大最后结果对1097取模。

样例输入

3 4 5 0

样例输出

1 2 4

解题思路这题题目也说了就是一道排列组合题。 有哪些组合可以让三份的糖果总数恰好能被三人均分   

1三份糖果 模3余数均为1 的 糖果

2三份糖果 模3余数均为2 的 糖果

3三份糖果 模3余数均为0 的 糖果

4一份糖果 模3余数为1 的 糖果  一份糖果 模3余数均为2 的 糖果 一份糖果 模3余数均为0 的 糖果。

最后对这4种情况的组合数求和就行了。   注意取模 和 爆int

AC代码

#include <stdio.h>const int Mod  1e97;int compute(__int64 s){                         // 组合数公式 C(n,3)    return (s*(s-1)*(s-2)/6) % Mod;}int main(){    int n,N;    __int64 x,y,z;    __int64 ans1,ans2,ans3,ans;    while (scanf(%d,&N) ! EOF && N ! 0)    {        x  N/3;                                // x:3的倍数的 个数        y  z  x;        n  N%3;        if (n  1)         y  1;             // y:模3余1的数 的个数        else if (n  2)    y  1, z  1;     // z:模3余2的数 的个数        ans1  compute(x);        ans2  compute(y);        ans3  compute(z);        ans  (ans1ans2ans3x*y*z) % Mod;        printf(%I64d\n,ans);    }    return 0;}