題意：給定A和B，A和B互質，求最大不能組合數，和不能組合數的個數。
基礎知識：
Gcd(A, B) = 1 → Lcm(A, B) = AB
剩余類，把所有整數劃分成m個等價類，每個等價類由相互同余的整數組成
任何數分成m個剩余類，分別為 mk，mk+1，mk+2，……，mk+(m-1)
分別記為{0(mod m)}，{1(mod m)}……
而n的倍數肯定分布在這m個剩余類中
因為Gcd(m，n)=1，所以每個剩余類中都有一些數是n的倍數，並且是平均分配它的旁證，可見HDOJ 1222 Wolf and Rabbit
設 kmin = min{ k | nk ∈ {i (mod m)} }, i ∈ [0, m)
則 nkmin 是{i (mod m)}中n的最小倍數。特別的，nm ∈ {0 (mod m)}
nkmin 是個標志，它表明{i (mod m)}中nkmin 後面所有數，即nkmin + jm必定都能被組合出來
那也說明最大不能組合數必定小於nkmin
我們開始尋找max{ nkmin }
Lcm(m, n) = mn，所以很明顯(m-1)n是最大的
因為(m-1)n是nkmin 中的最大值，所以在剩下的m-1個剩余類中，必定有比它小並且能被m和n組合，這些數就是(m-1)n -1，(m-1)n -2，……，(m-1)n -(m-1)
所以最大不能被組合數就是(m-1)n -m
如果m和n不互素，那{1 (mod m)}不能被m組合，同樣也不能被n和m組合
我們能求出各個剩余類的nkmin之後，不能組合數的個數就是每個剩余類中小於各自nkmin的數的個數總和。
觀察如下：
M = 5，N = 3
{0(mod 5)}：0，5，10，15……
{1(mod 5)}：1，6，11，16……
{2(mod 5)}：2，7，12，17……
{3(mod 5)}：3，8，13，18……
{4(mod 5)}：4，9，14，19……
紅色的就是不能組合數，可以看出在剩余類中它的數目有規律
Total = [0+1+2] + [0+1]
因為m和n互質，必有一個不完全周期
整理以後，可得公式 Total = (n-1)*(m-1)/2
[cpp]
#include<stdio.h>
int main()
{
int i,j,n,m;
while(scanf("%d%d",&n,&m)!=-1)
{
i=n*m-n-m;
j=(m-1)*(n-1)/2;
printf("%d %d\n",i,j);
}
return 0;
}
#include<stdio.h>
int main()
{
int i,j,n,m;
while(scanf("%d%d",&n,&m)!=-1)
{
i=n*m-n-m;
j=(m-1)*(n-1)/2;
printf("%d %d\n",i,j);
}
return 0;
}
