本文章为一些非常简单数论题的题解。

CF762A k-th divisor

题意：找到 $n$ 的第 $k$ 小因子。不存在输出 $-1$ 。

数据范围： $1\leq n\leq 10^{15}$ ， $1\leq k\leq 10^9$ 。

题解与代码

题解：注意到因子都是成对出现的。因此枚举 $[1,\sqrt{n}]$ 暴力判断即可。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	long long n,k,cnt=0,exist=0; 
	void yzmain()
	{
		scanf("%lld%lld",&n,&k);
		for(long long i=1;i*i<=n;i++)//暴力判断
			if(n%i==0)
			{
				cnt++;if(i*i==n) exist=1;//exist 判断是否存在两个相同数相乘为n
				if(cnt==k)
				{
					printf("%lld\n",i);
					return;
				}
			}
		cnt*=2;cnt-=exist;//算出因子数
		if(cnt<k)//不存在输出 -1
		{
			printf("-1\n");
			return;
		}
		for(long long i=1;i*i<=n;i++)//接着暴力判断
			if(n%(n/i)==0)
			{
				if(cnt==k)
				{
					printf("%lld\n",n/i);
					return;
				}
				cnt--;
			}
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

CF776B Sherlock and his girlfriend

题意：有 $n$ 个点，编号 $[2,n+1]$ ，给这些点染色，要求若 $a$ 是 $b$ 的质因子，则 $a$ 和 $b$ 的颜色不同，求一种颜色数最少的方案。

数据范围： $n\leq 10^5$ 。

题解与代码

题解：注意到质因子关系是二分图，一边是质数，一边是合数。把质数都染成 $1$ ，合数都染成 $2$ 即可。因此当 $n \leq 2$ 时，颜色数最少为 $1$ ，否则为 $2$ 。~~惊不惊喜，意不意外？~~

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	int n;
	int check(int x)
	{
		for(int i=2;i*i<=x;i++)
			if(x%i==0) return 2;
		return 1;
	}
	void yzmain()
	{
		scanf("%d",&n);
		if(n==1)
		{
			printf("1\n1");
			return;
		}
		if(n==2)
		{
			printf("1\n1 1");
			return; 
		}
		printf("2\n");
		for(int i=2;i<=n+1;i++)
			printf("%d ",check(i));
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

CF664A Complicated GCD

题意：给定整数 $a$ ， $b$ ，求 $\gcd(a, a+1, a+2, …, b)$ 。

数据范围： $1\leq a\leq b\leq10^{100}$ 。

题解与代码

题解：

设 $(a,b)$ 表示 $a,b$ 的最大公约数。

注意到， $(a+1,a)=(a,1)=(1,0)=1$ 。故当 $a < b$ 时，输出 $1$ ，否则输出 $a$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	string a,b; 
	void yzmain()
	{
		cin>>a>>b;
		if(a!=b) printf("1\n");
		else cout<<a;
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

CF757B Bash’s Big Day

题意：给定 $n$ 个正整数 $a_i$ 。求一个子集 $S$ ，满足 $\gcd(S_1,...,S_k)>1$ ，同时 $|S|$ 尽可能大。

数据范围： $1\leq n, a_i\leq 10^5$ 。

题解与代码

题解： $\gcd>1$ ，说明存在一个正整数 $d>1$ ，满足 $d$ 整除 $S$ 内的所有元素。枚举 $d \in [2,\max\{a_i\}]$ ，以桶的方式统计答案。设 $V=\max\{a_i\}$ ，时间复杂度为 $O(V \ln V)$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	int n,a[100000+5],ans=1,mx=0,tmp;
	int check(int k)
	{
		int ret=0;
		for(int i=k;i<=mx;i+=k)
			ret+=a[i];
		return ret;
	}
	void yzmain()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&tmp),mx=max(mx,tmp),a[tmp]++;
		for(int i=2;i<=mx;i++) ans=max(ans,check(i));
		printf("%d\n",ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

CF632D Longest Subsequence

题意：给出包含 $n$ 个数的数列 $A$ ，要求选出尽可能多的数，满足它们的最小公倍数不大于 $m$ 。允许不选，此时最小公倍数为 $1$ 。输出这个最小公倍数，选出数的个数，以及这些数在数列中的位置。

数据范围： $n,m\le{10}^{6}$ ， $a_i\le{10}^{9}$ 。

题解与代码

题解：

首先，注意到 $m\le10^6$ ，所以若 $a_i>m$ ，则 $a_i$ 可直接舍弃。好，我们成功地把数据范围由 $10^9$ 优化到 $10^6$ 了。

之后，如果数 $k$ 的约数集合为 $S$ ，则集合 $S$ 的最小公倍数一定小于等于 $k$ 。好，我们成功地把问题转化为求约数个数了。

我们可以枚举 $x\in[1,m]$ ，求数列 $A$ 中有多少数可整除 $x$ ，求个最大值。不过这样时间复杂度为 $O(nm)$ ，超时。我们可以把这个过程转换一下，枚举 $x\in A$ ，看 $x$ 能为 $[1,m]$ 中的哪些数做贡献。很明显， $x$ 可为所有为 $x$ 的倍数的数做贡献（当然要小于 $m$ ）。好，我们成功地降低时间复杂度为 $O(n\log m)$ 了。

此算法可通过本题。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=1000000+10;
	int a[N],num[N],n,m,ans[N],v[N],lcm=1,cnt=0;
	void yzmain()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) 
		{
			scanf("%d",a+i);
			if(a[i]<=m) num[a[i]]++;//忽略大于m的数，使用桶统计数的个数
		}
		for(int i=1;i<=n;i++)
		{
			if(a[i]>m || v[a[i]]) continue;//数大于m || 重复数
			for(int j=1;j*a[i]<=m;j++)
				ans[a[i]*j]+=num[a[i]];//统计贡献
			v[a[i]]=1;//去重
		}
		for(int i=1;i<=m;i++)
			if(ans[i]>cnt) lcm=i,cnt=ans[i];//保证是**最小**公倍数
		printf("%d %d\n",lcm,cnt);
		for(int i=1;i<=n;i++)
			if(lcm%a[i]==0) printf("%d ",i);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P1445 [Violet]樱花

题意：给定 $n$ ，求方程 $\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n!}$ 的正整数解的组数，答案对 $10^9+7$ 取模。 $1\le n \le10^6$ 。

点击查看题解

题解：看着这个式子，什么玩意！不过可以对式子进行变形：

\begin{aligned} \dfrac{1}{x} + \dfrac{1}{y} &= \dfrac{1}{n!}\\\\ xn! + yn! &= xy\\\\ 0 &= - xn! - yn! + xy\\\\ (n!)^2 &= (n!)^2 -xn! -yn! +xy\\\\ (n!)^2 &= (x-n!)(y-n!)\\\\ \end{aligned}

发现，每一组 $x$ 和 $y$ 都唯一对应着 $(n!)^2$ 的因子。

所以，此题转化为，求 $(n!)^2$ 的因子个数。

算术基本定理： $N = \prod\limits_{i=1}^k p_i^{e_i}$ 。 $p_i$ 为质数。这样的分解是唯一的。

因数个数： $M = \prod\limits_{i=1}^k (e_i+1)$ 。可以推出 $M^2 = \prod\limits_{i=1}^k (2e_i+1)$ 。排列组合和乘法原理可证。

附加题：求 $\sum x_i+y_i$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace name
{
	typedef long long ll;
	const ll mod=1000000007,N=1000000+10;
	ll n,prime[N],p[N],e[N],ans=1,cnt=0;
	void getPrime(ll n)
	{
		for(ll i=2;i<=n;i++)
		{
			if(!p[i]) prime[++cnt]=i,p[i]=i;
			for(ll j=1;j<=cnt;j++)
			{
				if(prime[j]>p[i]||prime[j]>n/i) break;
				// 保证 prime_j 是最小质因数 || 不要超过 n 
				p[i*prime[j]]=prime[j];
			}
		}
		return;
	}
	void main()
	{
		scanf("%lld",&n);
		getPrime(n);
		for(ll i=1;i<=n;i++)
		{
			for(ll j=i;j>=2;j/=p[j])
				e[p[j]]++;
		}
		for(ll i=2;i<=n;i++)
			ans=(ans*(e[i]*2%mod+1))%mod;
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	name::main();
	return 0;
}

P1072 [NOIP2009 提高组] Hankson 的趣味题

题意：已知正整数 $a_0$ ， $a_1$ ， $b_0$ ， $b_1$ ，设某未知正整数 $x$ 满足：

$x$ 和 $a_0$ 的最大公约数是 $a_1$ ；
$x$ 和 $b_0$ 的最小公倍数是 $b_1$ 。

求解满足条件的 $x$ 的个数。保证有 $1 \leq a_0,a_1,b_0,b_1 \leq 2 \times 10^9$ ， $n\le2000$ 且 $a_1|a_0$ ， $b_0|b_1$ 。

点击查看题解

题解：

$\gcd(a,b) = c \Rightarrow \gcd(a/c,b/c) = 1$ （显然 / 反证）。
$\operatorname{lcm}(a,b) = c \Rightarrow \gcd(a,b) = a\times b/c \Rightarrow \gcd(a/(a\times b/c),b/(a\times b/c)) = 1 \Rightarrow \gcd(c/b,c/a) = 1$ 。

现在应用这两个结论。

$\gcd(x,a_0) = a_1\Rightarrow \gcd(x/a_1,a_0/a_1) = 1$ 。
$\operatorname{lcm}(x,b_0) = b_1 \Rightarrow \gcd(b_1/x,b_1/b_0) = 1$ 。

输入数据保证 $a_0$ 能被 $a_1$ 整除， $b_1$ 能被 $b_0$ 整除。故枚举 $x$ （ $b_1$ 因子）即可。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace name
{
	typedef long long ll;
	ll a0,a1,b0,b1,ans;
	ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
	ll check(ll x)
	{
		if(x%a1!=0) return 0;
		if(gcd(x/a1,a0/a1)!=1) return 0;
		if(gcd(b1/x,b1/b0)!=1) return 0;
		return 1;
	}
	void main()
	{
		ll T;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld%lld%lld%lld",&a0,&a1,&b0,&b1);
			ans=0;
			for(ll i=1;i*i<=b1;i++)
			{
				if(b1%i) continue;
				if(check(i)) ans++;
				ll j=b1/i;
				if(i==j) break;
				if(check(j)) ans++;
				
			}
			printf("%lld\n",ans);
		} 
		return;
	}
}
int main()
{
	name::main();
	return 0;
}

P3197 [HNOI2008]越狱

题意

监狱有 $n$ 个房间，每个房间关押一个犯人，有 $m$ 种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对 $100003$ 取模。

对于 $100\%$ 的数据，保证 $1 \le m \le 10^8$ ， $1 \le n \le 10^{12}$ 。

点击查看题解

题解

发生越狱数 $=$ 总数 $-$ 不发生越狱数。

总数：每个房间有 $m$ 种宗教可选，故为 $m^n$ 。

不发生越狱数：第一个房间信什么都行，第二个不能信第一个信的那个，第三个不能信第二个信的那个……故为 $m\times(m-1)^{n-1}$ 。

所以答案为： $m^n-m\times(m-1)^{n-1}$ 。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll mod=100003; 
	ll n,m,ans=0;
	ll pow(ll a,ll b)
	{
		ll ret=1;
		while(b)
		{
			if(b%2) ret=ret*a%mod;
			a=a*a%mod; b/=2;
		}
		return ret;
	}
	void main()
	{
		scanf("%lld%lld",&m,&n);
		ans=pow(m,n);
		ans=((ans-(m*pow(m-1,n-1)))%mod+mod)%mod;
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}

小白鼠保护协会的孤注一掷

2023-08-14 不想改格式。

题目背景

邪恶的 xytz 又双叒要拿小白鼠做实验了，身为小白鼠保护协会的你要尽自己最大可能去保护它们。

题目描述

xytz 有 $n$ 瓶药，有一瓶过期了（过期药有毒），需要用多只小白鼠来测试哪一瓶药过期，过期药 24h 毒效发作，问：保证在时间最短的前提下，最少用多少只小白鼠。

输入格式

输入一个正整数 $n$ ，表示需要测试多少瓶药。

输出格式

输出一个正整数 $m$ ，表示在时间最短的前提下，最少用多少只小白鼠。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $40\%$ 的数据， $1\le n\le 10^9$ ；

对于 $100\%$ 的数据， $1\le n\le 10^{18}$ 。

题解

信息论。把 $n$ 瓶药编号，如果其编号在二进制下第 $i$ 位为 $1$ ，就让第 $i$ 个小白鼠吃。这样看死亡情况即可推知是哪瓶药有毒。

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/e4b4986bb6ee/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 数论毒瘤题一些唯一分解

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158

一些简单数论题

CF762A k-th divisor

CF776B Sherlock and his girlfriend

CF664A Complicated GCD

CF757B Bash’s Big Day

CF632D Longest Subsequence

P1445 [Violet]樱花

P1072 [NOIP2009 提高组] Hankson 的趣味题

P3197 [HNOI2008]越狱

题意

题解

代码

小白鼠保护协会的孤注一掷

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

题解