三元组

也许更好的阅读体验
$Description$Description
给定 $n,k$n,k,对于一 个三元组 $(a,b,c)$(a,b,c),若合法则需要满足 $1\le a,b,c\le n$1≤a,b,c≤n,且两两元素之和均为 $k$k的倍数。
求不同的合法的三元组有多少个。
三元组的相应的任意一 位不同则认为他们不同。
$Solution$Solution
设 $a=x_{1}k,b=x_{2}k,c=x_{3}k$a=x1​k,b=x2​k,c=x3​k
$x1,x2,x3\in [0,n/k]$x1,x2,x3∈[0,n/k] (包括小数)
则有
$a+b=(x_1+x_2)k$a+b=(x1​+x2​)k
$b+c=(x_2+x_3)k$b+c=(x2​+x3​)k
$a+c=(x_1+x_3)k$a+c=(x1​+x3​)k
即
$x_1+x_2\in Z$x1​+x2​∈Z
$x_2+x_3\in Z$x2​+x3​∈Z
$x_1+x_3\in Z$x1​+x3​∈Z
所以可以知道

• 若 $x1,x2,x3\in Z$x1,x2,x3∈Z
  则 $x1,x2,x3$x1,x2,x3有 $n/k$n/k种选择
  • 当三个数字全部不相同　有 $C_{n/k}^3$Cn/k3​种搭配，每种搭配有６种排列方式
  • 当三个数字有两个相同　有 $C_{n/k}^2$Cn/k2​种搭配，每种搭配有６种排列方式
  • 当三个数字全部都相同　有 $n/k$n/k种搭配，每种搭配有１种排列方式
• 若 $x1,x2,x3\notin Z$x1,x2,x3∈/​Z
  又 $\because x1,x2,x3$∵x1,x2,x3两两相加为整数
  $\therefore x1,x2,x3=ik+\frac{k}{2},i\in Z$∴x1,x2,x3=ik+2k​,i∈Z
  此时条件 $k\%2==0$k%2==0
  则 $x1,x2,x3$x1,x2,x3有 $n/\frac{k}{2}-n/k$n/2k​−n/k种选择
  接下来的计算同上

代码

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年06月13日 星期四 08时19分25秒 *******************************/
#include <cstdio>
#include <fstream>
#define ll long long
using namespace std;
int n,k,tim,hal;
ll ans;
ll C3 (int n) { return 1ll*n*(n-1)/2*(n-2)/3; }
ll C2 (int n) { return 1ll*n*(n-1)/2; }
int main()
{
	scanf("%d%d",&n,&k);
	tim=n/k;
	if ((k-1)&1){
		hal=n/(k/2)-tim;
		ans+=6*C3(hal)+6*C2(hal)+hal;
	}
	ans+=6*C3(tim)+6*C2(tim)+tim;
	printf("%lld\n",ans);
	return 0;
}