AtCoder Regular Contest 102 C - Triangular Relationship（数论、同余）

题目链接

https://arc102.contest.atcoder.jp/tasks/arc102_a

题意

给定N和K。
求三元组（a，b，c）的个数。
三元组满足下面条件：
a、b、c的值都是不大于N的正整数。
a+b、b+c、a+c都是K的整数倍。

题解

根据数论同余的知识：
a mod K + b mod K = K mod K.
b mod K + c mod K = K mod K.
a mod K + c mod K = K mod K.
解得a=b=c=K/2 mod K（当K是偶数时有解）。或者a=b=c=K mod K。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;int a[maxn];//各个同余系的个数int main()
{int n,k;while(~scanf("%d%d",&n,&k)){for(int i=1;i<=k;i++){a[i]=n/k;}int r=n%k;for(int i=1;i<=r;i++) a[i]++;ll ans=0;ans+=(ll)a[k]*(ll)a[k]*(ll)a[k];if(k%2==0)ans+=(ll)a[k/2]*(ll)a[k/2]*(ll)a[k/2];printf("%lld\n",ans);}return 0;
}