本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191170.html

D2T1 点指兵兵

题目

你一定有过在两个物品之间犹豫不决的时候，想要借助一些方法帮你随机选择。

在广东，有一种方法叫”点指兵兵”，即一开始用手指指向一个物品，然后念” 点指兵兵点到谁人做大兵”，从第二个字开始，每念一个字，手指就移动到另一个物品上。

整句话念完，手指指向谁，你就选择谁。

但很快你就发现，这个方法是有问题的——你最终指向的物品一定是你一开始指向的物品，这严重破坏了这个方法的随机性。

后来你学了信息学，你更加清楚这个规律了，咒语长度是奇数的时候最终指向跟初始指向相同，咒语长度是偶数的时候最终指向跟初始指向不同。

所以解决的方法有这么几种：

  • 增加咒语长度，可以念一句很长很长的句子，长到你也数不清是奇数还是偶数。
  • 增加物品数量，只有两个物品的话规律太多，多一些物品也就少一些规律。

因此现在你面对的问题是这样的：有若干个物品（至少 3 个）排成一圈，你要念一句长度为 n(n≥3)n (n ≥ 3) 的咒语，一开始手指指向任意一个物品，从第二个字开始，每念一个字，手指移动到顺时针的下一个物品。

如果最终指向的物品不是初始指向的物品，也不是与初始物品相邻的物品，那么就认为这个选择是比较随机的。

给定 nn，你想知道 3,…,n3, \dots, n 这些数字有多少个作为物品数量的时候，选择是比较随机的。

思路

假如现在有 kk 个物品，要指到自己本身，则必须满足 n mod k=1n\bmod k=1，也就是 (n−1) mod k=0(n-1)\bmod k=0。

如果指到下一个，则满足 n mod k=2n\bmod k=2，即 (n−2) mod k=0(n-2)\bmod k=0。

如果指到上一个，则 n mod k=0n\bmod k=0。

那结果就是 nn 减去不符合要求的数目，也就是 n,n−1,n−2n, n-1, n-2 的因数，因为这三个数任意两数的gcd必然小于3，所以可以直接 O(n)O(\sqrt n) 求一遍就行。

小数据最好特判一下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'
){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x
<<3)+(ch^48);ch=getchar();}return x*f;}
//#define N
//#define M
//#define mo
int n, m, i, j, k, T;

void suan(int x)
{
	for(int i=1; i*i<=x; ++i)
	{
		if(x%i) continue; 
		if(i>3) ++m; 
		if(x/i>3 && i*i!=x) ++m; 
	}
//	printf("%lld\n", m); 
}

signed main()
{
	
	T=read(); 
	while(T--)
	{
		n=read(); m=3; 
		if(n<=5) 
		{
			printf("0\n"); 
			continue; 
		}
		suan(n); suan(n-1); suan(n-2); 
		printf("%lld\n", n-m); 
	}
	return 0;
}

总结

这道题难度不大，但注重细节。

对于小于等于3的情况，一定要特判好。

类似涉及这些质数因数的题目一定要注意小数据。