284.轻拍牛头
题目:
今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。
贝茜让 N 头奶牛（编号1到N）坐成一个圈。
除了 1 号与 N 号奶牛外，i 号奶牛与 i - 1 号和 i + 1 号奶牛相邻，N 号奶牛与 1 号奶牛相邻。农夫约翰用很多纸条装满了一个桶，每一张纸条中包含一个 1 到 1000000 之间的数字。
接着每一头奶牛 i 从桶中取出一张纸条，纸条上的数字用Aᵢ表示。
所有奶牛都选取完毕后，每头奶牛轮流走上一圈，当走到一头奶牛身旁时，如果自己手中的数字能够被该奶牛手中的数字整除，则拍打该牛的头。
牛们希望你帮助他们确定，每一头奶牛需要拍打的牛的数量。
即共有 N 个整数 A₁，A₂，...，Aɴ，对于每一个数Aᵢ，求其他的数中有多少个是它的约数。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个整数 Aᵢ。
输出格式
共 N 行，第 i 行的数字为第 i 头牛需要拍打的牛的数量。
数据范围
1≤N≤10⁵
1≤Aᵢ≤10⁶
输入样例:
5
2
1
2
3
4
输出样例:
2
0
2
1
3
思路:
1.如何求约数个数呢？如果N=P₁ᶜ¹×P₂ᶜ²×……×Pₖᶜᵏ。那么约数个数f(N)＝(c₁+1)(c₂+1)……(cₖ+1)。
2.那1～N中，每一个数的约数个数之和是什么数量级呢？也就是∑f(i)(i:1→N)。1是N/1个数的约数，2是N/2个数的约数……由调和级数可知，最后∑f(i)(i:1→N)就是NlogN的一个级别。
3.我们还需要知道，在int范围内，约数个数最大的数拥有的约数个数为1536个。
4.本道题目不用公式，直接求即可。如果正向求，也就是分别求每个数的约数个数的话，时间复杂度会非常大。本题反向求即可，也就是求有多少个数是这个数的倍数即可。
代码(c++):
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n;
int a[N], cnt[N], s[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
cnt[a[i]] ++ ; //a[i]出现的次数
}
for (int i = 1; i < N; i ++ )
for (int j = i; j < N; j += i)
s[j] += cnt[i];
for (int i = 0; i < n; i ++ ) printf("%d\n", s[a[i]] - 1);
return 0;
}
285.樱花
题目:
给定一个整数n，求有多少正整数数对(x，y)满足1/x+1/y=1/n!。
输入格式
一个整数n。
输出格式
一个整数，表示满足条件的数对数量。
答案对10⁹+7取模。
数据范围
1≤n≤10⁶
输入样例:
2
输出样例:
3
样例解释
共有三个数对(x，y)满足条件，分别是(3，6)，(4，4)，(6，3)。
思路:
1.我们先把题目的式子整理一下，得到x×n!+y×n!＝xy。进一步，x×n!＝(n!-x)×y。进一步，y＝(x×n!)/(x-n!)。进一步，y＝n!+n!²/(x-n!)。也就是正整数里有多少个正整数x，使得y也是正整数。
2.首先如果x≤n!的话，y就会是负数，那么和题目里y是正整数矛盾。所以x大于等于n!。分母x-n!一定是正数，所以满足条件的x的个数就等于满足条件的x-n!的个数，所以就等价于n!²的约数个数。答案就为f(N)＝(2c₁+1)(2c₂+1)……(2cₖ+1)。
代码(c++):
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, mod = 1e9 + 7;
int primes[N], cnt;
bool st[N];
void init(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] * i <= n; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main()
{
int n;
cin >> n;
init(n);
int res = 1;
for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];
int s = 0;
for (int j = n; j; j /= p) s += j / p;
res = (LL)res * (2 * s + 1) % mod;
}
cout << res << endl;
return 0;
}
286.反素数
题目:
对于任何正整数x，其约数的个数记作g(x)，例如g(1)=1、g(6)=4。
如果某个正整数满足：对于任意的小于x的正整数i，都有g(x)>g(i)，则称x为反素数。例如，整数1，2，4，6等都是反素数。
现在给定一个数N，请求出不超过N的最大的反素数。
输入格式
一个正整数N。
输出格式
一个整数，表示不超过N的最大反素数。
数据范围
1≤N≤2×10⁹
输入样例:
1000
输出样例:
840
思路:
1.反素数就是指定范围内所有约数个数最多的最小的数。不同的质因子最多几个呢？我们先算一下2*3*5*7*11*13*17*19*23=223092870，所以不同的质因子最多有9个。每个质因子的次数最大是30，因为2³¹为2147483648，已经严格大于本题的数据范围了。最后，所有质因子的次数一定是非严格递减的。否则，假设某个数是2ᵃ×3⁵×5⁶×……，那么把3和5的指数调换一下就可以构造出来一个约数个数和原数相同，但是整体数值却更小的一个数，也就是2ᵃ×3⁶×5⁵×……。
2.所以本道题其实直接爆搜即可。
代码(c++):
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int primes[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int maxd, number;
int n;
void dfs(int u, int last, int p, int s) //枚举到第几个质数，次数最大是多少(本题为30)，当前累积的乘积是多少，约数个数
{
if (s > maxd || s == maxd && p < number)
{
maxd = s;
number = p;
}
if (u == 9) return;
for (int i = 1; i <= last; i ++ )
{
if ((LL)p * primes[u] > n) break;
p *= primes[u];
dfs(u + 1, i, p, s * (i + 1)); //枚举下一个质数，当前质数的次数(也就是下一个质数最大的次数)，当前累积的乘积，约数个数(根据公式f(N)=(c₁+1)(c₂+1)……(cₖ+1)得到)
}
}
int main()
{
cin >> n;
dfs(0, 30, 1, 1);
cout << number << endl;
return 0;
}
287.Hankson的趣味题
题目:
Hanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson,现在，刚刚放学回家的Hankson正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数c₁和c₂的最大公约数和最小公倍数。
现在Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：
已知正整数a₀，a₁，b₀，b₁，设某未知正整数x满足：
1、x和a₀的最大公约数是a₁；
2、x和b₀的最小公倍数是b₁。
Hankson的“逆问题”就是求出满足条件的正整数x。
但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。
请你帮助他编程求解这个问题。
输入格式
输入第一行为一个正整数n，表示有n组输入数据。
接下来的n行每行一组输入数据，为四个正整数a₀，a₁，b₀，b₁，每两个整数之间用一个空格隔开。
输入数据保证a₀能被a₁整除，b₁能被b₀整除。
输出格式
输出共n行。
每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的x，请输出0；
若存在这样的x，请输出满足条件的x的个数；
数据范围
1≤n≤2000
1≤a₀, a₁, b₀, b₁≤2×10⁹
输入样例:
2
41 1 96 288
95 1 37 1776
输出样例:
6
2
思路:
1.如何找到所有x满足(a,x)=b，[c,x]=d呢？我们可以枚举d的所有约数，对于每个约数d判断一下等式是否成立即可。对于(a,x)我们直接调用gcd函数即可。对于[c,x]，[c,x]＝cx/(c,x)，也可以用gcd来判断。而根据之前2×10⁹以内约数个数最多的数的约数个数为1536。一共最大2000组测试数据，而欧几里得算法时间复杂度为O(logmin(a, b))，这里为O(logx)。所以时间复杂度最终为3.2×10⁶×logx。
2.那怎么去枚举约数呢？我们知道枚举d的所有约数时间复杂度为O(√d)，所以上面的方法很可能会超时。所以我们应该换一种方法。我们去枚举所有质数即可，也就是相当于先将d分解质因数，然后再用这些质因子去组合成每一个约数。分解质因数可以让时间复杂度降低，原来需要√d，此处d最大为2×10⁹。而我们只枚举质数，根据质数定理，时间复杂度变为√d/lnd，将近使得时间复杂度降低为原来的1/10。
代码(c++):
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 50010;
int primes[N], cnt;
bool st[N];
struct Factor
{
int p, s;
}factor[10]; //p是质因子，s是次数
int fcnt; //质因子的个数
int dividor[1601], dcnt; //约数，约数个数
void init(int n) //线性筛法求质数
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] * i <= n; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
void dfs(int u, int p) //先枚举每个质因子，再枚举该质因子的次数。这里u代表第u个质因子，p代表乘积
{
if (u == fcnt) //如果u是最后一个质因子了，那么我们直接存下来
{
dividor[dcnt ++ ] = p;
return;
}
for (int i = 0; i <= factor[u].s; i ++ ) 否则枚举当前质因子的次数，从0次开始
{
dfs(u + 1, p); //递归到下一个质数
p *= factor[u].p;
}
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
init(N - 1);
int n;
cin >> n;
while (n -- )
{
int a, b, c, d;
cin >> a >> b >> c >> d;
fcnt = 0;
int t = d;
for (int i = 0; primes[i] <= t / primes[i]; i ++ )
{
int p = primes[i];
if (t % p == 0)
{
int s = 0;
while (t % p == 0) t /= p, s ++ ;
factor[fcnt ++ ] = {p, s};
}
}
if (t > 1) factor[fcnt ++ ] = {t, 1}; //如果t＞1，说明t本身也是一个质因子
dcnt = 0;
dfs(0, 1); //暴搜，枚举质因子和当然质因子的次数。根据质因子去组成约数，0为第0个质因子，1为当前乘积
int res = 0;
for (int i = 0; i < dcnt; i ++ ) //枚举约数
{
int x = dividor[i];
if (gcd(a, x) == b && (LL)c * x / gcd(c, x) == d) res ++ ;
}
cout << res << endl;
}
return 0;
}
288.可见的点
题目:
在一个平面直角坐标系的第一象限内，如果一个点(x, y)与原点(0, 0)的连线中没有通过其他任何点，则称该点在原点处是可见的。
例如，点(4, 2)就是不可见的，因为它与原点的连线会通过点(2, 1)。部分可见点与原点的连线如下图所示：
编写一个程序，计算给定整数N的情况下，满足0≤x, y≤N的可见点(x, y)的数量（可见点不包括原点）。
输入格式
第一行包含整数C，表示共有C组测试数据。每组测试数据占一行，包含一个整数N。
输出格式
每组测试数据的输出占据一行。
应包括：测试数据的编号（从1开始），该组测试数据对应的N以及可见点的数量。
同行数据之间用空格隔开。
数据范围
1≤N,C≤1000
输入样例:
4
2
4
5
231
输出样例:
1 2 5
2 4 13
3 5 21
4 231 32549
思路:
1.我们先回忆一下欧拉函数，欧拉函数的定义是1～N中和N互质的数的个数。φ(N)=N×(1-1/p₁)×……×(1-1/pₖ)。其中pₖ是将N分解质因数后的质因子。当N是1时，它的欧拉函数是1。如果N是质数，那么它的欧拉函数是N-1。如果pⱼ能整除i。那么φ(i×pⱼ)和φ(i)的关系为φ(i×pⱼ)＝pⱼ×φ(i)。如果pⱼ不能整i，那么φ(i×pⱼ)和φ(i)的关系为φ(i×pⱼ)＝(pⱼ-1)×φ(i)。
2.本题能被看见的点有什么性质呢？应该满足y＝kx的直线上，并且是这条线上从(0, 0)开始走的第一个点。假设这个点是(x₀,y₀)，那么这条直线就是y＝(y₀/x₀)×x。那么第一个点有什么性质呢？它的性质为x₀和y₀互质，否则x₀和y₀存在一个因子d，使得(x₀/d, y₀/d)在(x₀, y₀)更左下的位置。
3.所以这道题本质就是求欧拉函数。我们把上图由y＝x划分为上下两部分。那么下半部分可见点数量为φ(1)+……+φ(N)，同理上半部分也是这些。再加上y＝x的直线上有一个点。答案就是2×[φ(1)+……+φ(N)]+1。
代码(c++):
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int primes[N], cnt;
bool st[N];
int phi[N];
void init(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
phi[i] = i - 1;
}
for (int j = 0; primes[j] * i <= n; j ++ )
{
st[i * primes[j]] = true;
if (i % primes[j] == 0)
{
phi[i * primes[j]] = phi[i] * primes[j]; //i能整除primes[j]
break;
}
phi[i * primes[j]] = phi[i] * (primes[j] - 1); //i不能整除primes[j]
}
}
}
int main()
{
init(N - 1);
int n, m;
cin >> m;
for (int T = 1; T <= m; T ++ )
{
cin >> n;
int res = 1; //y＝x上的可见的点
for (int i = 1; i <= n; i ++ ) res += phi[i] * 2;
cout << T << ' ' << n << ' ' << res << endl;
}
return 0;
}
289.最大公约数
题目:
给定整数N，求1<=x, y<=N且GCD(x, y)为素数的数对(x, y)有多少对。GCD(x, y)即求x，y的最大公约数。
输入格式
输入一个整数N
输出格式
输出一个整数，表示满足条件的数对数量。
数据范围
1≤N≤10⁷
输入样例：
4
输出样例：
4
思路:
1.我们可以枚举1～N中的所有质数P。求一下x和y都在1～N中，并且最大公约数是P的数对，那么就等价于(x/P, y/P)＝1。设x/P为x'，y/P为y'。所以就等价于1≤x', y'≤N/P的条件下，(x', y')＝1的数对个数。由下图可知，答案为2×[φ(2)+……+φ(N/P)]+1。
代码(c++):
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
int primes[N], cnt;
bool st[N];
int phi[N];
LL s[N];
void init(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
phi[i] = i - 1;
}
for (int j = 0; primes[j] * i <= n; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0)
{
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
}
}
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + phi[i];
}
int main()
{
int n;
cin >> n;
init(n);
LL res = 0;
for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];
res += s[n / p] * 2 + 1;
}
cout << res << endl;
return 0;
}
