UVa 10292 The Gossiping System

题目描述

在

Knoxville

\\texttt{Knoxville}

Knoxville 镇，居民们喜欢传播谣言。为了在不完全破坏这种乐趣的同时建立秩序，他们制定了一套系统，使谣言以受控方式传播。居民们每天以小组形式聚会，系统满足以下三个条件：

这样的系统称为

(

n

,

g

,

m

,

r

)

(n,g,m,r)

(n,g,m,r) -谣言传播系统，其中

n

n

n 是总人数，

g

g

g 是小组数，

m

m

m 是每个小组的人数，

r

r

r 是每个人所属的小组数。

本题只研究

r

=

2

r = 2

r=2 的情况，即每个人恰好属于两个小组。给定人数

n

n

n （

1

<

n

<

10

50

1 < n < 10^{50}

1<n<1050 ），判断是否存在这样的

(

n

,

g

,

m

,

2

)

(n,g,m,2)

(n,g,m,2) -谣言传播系统（存在正整数

g

>

1

g > 1

g>1 和

m

>

0

m > 0

m>0 使得系统存在）。如果存在，输出 Yes. ，否则输出 No. 。

题目分析

这是一个组合设计问题。我们需要判断是否存在满足以下条件的系统：

• $n$
• 每个小组 $m$
• 每个人属于恰好 $2$
• 任意两个不同小组恰好有 $1$

数学模型建立

这种结构在组合设计中可以看作一种特殊的超图（

hypergraph

\\texttt{hypergraph}

hypergraph）或区组设计（

block

design

\\texttt{block design}

block design） 。设：

• $n$
• $g$
• $m$
• $r=2$

根据条件可得基本关系式：

构造法分析

通过观察和构造，我们可以发现一种有效的构造方法：利用完全图

K

k

K_k

Kk​ 的边作为顶点。

构造方法：

验证参数关系：

• $n=\frac{k(k-1)}{2}$
• $g=k$
• $m=k-1$
• $r=2$

满足

2

n

=

g

m

2n = gm

2n=gm ：左边

2

×

k

(

k

−

1

)

2

=

k

(

k

−

1

)

2 \\times \\frac{k(k-1)}{2} = k(k-1)

2×2k(k−1)​=k(k−1) ，右边

g

×

m

=

k

×

(

k

−

1

)

g \\times m = k \\times (k-1)

g×m=k×(k−1) ，成立。

必要条件推导

反过来，我们证明：如果存在满足条件的系统，那么

n

n

n 必须是一个三角形数，即

n

=

(

k

2

)

n = \\binom{k}{2}

n=(2k​) 对某个整数

k

≥

2

k \\ge 2

k≥2 。

考虑关联矩阵

M

M

M （

n

×

g

n \\times g

n×g 的

0

0

0 –

1

1

1 矩阵，

M

i

j

=

1

M_{ij}=1

Mij​=1 表示人

i

i

i 在小组

j

j

j 中）。条件可转化为：

设

A

=

M

T

M

A = M^T M

A=MTM ，则

A

A

A 是

g

×

g

g \\times g

g×g 矩阵，其对角线元素为

m

m

m ，非对角线元素为

1

1

1 。即

A

=

J

+

(

m

−

1

)

I

A = J + (m-1)I

A=J+(m−1)I ，其中

J

J

J 是全

1

1

1 矩阵，

I

I

I 是单位矩阵。

可以证明，这样的矩阵

A

A

A 只有当

g

=

m

g = m

g=m 或

g

=

m

+

1

g = m+1

g=m+1 等特殊情况下才能满足正定性等条件。通过详细推导（涉及矩阵特征值分析），最终可得

n

n

n 必须满足

n

=

k

(

k

−

1

)

2

n = \\frac{k(k-1)}{2}

n=2k(k−1)​ 的形式。具体推导较复杂，这里从略。

判定条件

综上所述，存在

(

n

,

g

,

m

,

2

)

(n,g,m,2)

(n,g,m,2) -谣言传播系统 当且仅当

n

n

n 是三角形数，即存在整数

k

≥

2

k \\ge 2

k≥2 使得：

n

=

k

(

k

−

1

)

2

n = \\frac{k(k-1)}{2}

n=2k(k−1)​

等价地，

8

n

+

1

8n+1

8n+1 必须是一个完全平方数。因为：

n

=

k

(

k

−

1

)

2

⟹
  

k

2

−

k

−

2

n

=

0

n = \\frac{k(k-1)}{2} \\implies k^2 – k – 2n = 0

n=2k(k−1)​⟹k2−k−2n=0 判别式

Δ

=

1

+

8

n

\\Delta = 1 + 8n

Δ=1+8n 必须为完全平方数，且

k

=

1

+

1

+

8

n

2

k = \\frac{1 + \\sqrt{1+8n}}{2}

k=21+1+8n

​​ 为正整数。

判定算法： 对于输入的

n

n

n ，计算

D

=

8

n

+

1

D = 8n + 1

D=8n+1 ，判断

D

D

D 是否为完全平方数。如果是，则输出 Yes. ，否则输出 No. 。

样例验证

解题思路

关键点：

• 大数运算：乘法、加法、比较、开平方。
• 使用二分法求平方根，避免超时。
• 注意 $n$

时间复杂度

• 大数乘法： $O(L^2)$
• 二分法求平方根： $O(L\log N)$
• 总体在可接受范围内。

空间复杂度

• 主要存储大数字符串： $O(L)$

代码实现

// The Gossiping System
// UVa ID: 10292
// Verdict: Accepted
// Submission Date: 2026-01-11
// UVa Run Time: 0.050s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

// 比较两个大数字符串，a >= b 返回 true
bool greaterOrEqual(const string& a, const string& b) {
if (a.length() != b.length()) return a.length() > b.length();
return a >= b;
}

// 大数加法
string addStrings(const string& a, const string& b) {
string result = "";
int i = a.length() – 1, j = b.length() – 1, carry = 0;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += a[i—] – '0';
if (j >= 0) sum += b[j—] – '0';
result = char(sum % 10 + '0') + result;
carry = sum / 10;
}
return result;
}

// 大数减法（保证 a >= b）
string subtractStrings(const string& a, const string& b) {
string result = "";
int i = a.length() – 1, j = b.length() – 1, borrow = 0;
while (i >= 0) {
int digit = (a[i—] – '0') – borrow;
if (j >= 0) digit -= (b[j—] – '0');
if (digit < 0) {
digit += 10;
borrow = 1;
} else borrow = 0;
result = char(digit + '0') + result;
}
size_t pos = result.find_first_not_of('0');
if (pos == string::npos) return "0";
return result.substr(pos);
}

// 大数除以2（整除）
string divideByTwo(const string& a) {
string result = "";
int remainder = 0;
for (char digit : a) {
int current = remainder * 10 + (digit – '0');
result += char(current / 2 + '0');
remainder = current % 2;
}
size_t pos = result.find_first_not_of('0');
if (pos == string::npos) return "0";
return result.substr(pos);
}

// 大数乘以一位数
string multiplyByDigit(const string& a, int digit) {
if (digit == 0) return "0";
string result = "";
int carry = 0;
for (int i = a.length() – 1; i >= 0; i—) {
int product = (a[i] – '0') * digit + carry;
result = char(product % 10 + '0') + result;
carry = product / 10;
}
if (carry > 0) result = char(carry + '0') + result;
return result;
}

// 大数乘法
string multiplyStrings(const string& a, const string& b) {
if (a == "0" || b == "0") return "0";
string result = "0";
int zeros = 0;
for (int i = b.length() – 1; i >= 0; i—) {
string partial = multiplyByDigit(a, b[i] – '0');
partial += string(zeros, '0');
result = addStrings(result, partial);
zeros++;
}
return result;
}

// 判断一个数是否为完全平方数，如果是则返回平方根字符串，否则返回"0"
string isPerfectSquare(const string& num) {
if (num == "0" || num == "1") return num;
string low = "1", high = num;
while (greaterOrEqual(high, low)) {
string mid = divideByTwo(addStrings(low, high));
string square = multiplyStrings(mid, mid);
if (square == num) return mid;
if (greaterOrEqual(square, num)) high = subtractStrings(mid, "1");
else low = addStrings(mid, "1");
}
return "0";
}

// 判断是否存在(n,g,m,2)-gossiping system
bool isGossipSystemPossible(const string& nStr) {
// 计算 8*n
string eightN = multiplyByDigit(nStr, 8);
// 计算 8*n + 1
string value = addStrings(eightN, "1");
// 检查是否为完全平方数
return isPerfectSquare(value) != "0";
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t—) {
string nStr;
cin >> nStr;
if (isGossipSystemPossible(nStr)) cout << "Yes.\\n";
else cout << "No.\\n";
}
return 0;
}

总结

本题的关键在于将组合设计问题转化为数论问题，发现系统存在的充要条件是

n

n

n 为三角形数。通过构造法证明充分性，通过矩阵分析证明必要性。实现时需注意大数运算，特别是判断大数是否为完全平方数的高效算法。最终算法简洁高效，能够处理

n

n

n 高达

10

50

10^{50}

1050 的情况。