Codeforces Round #304 (Div. 2) D. Soldier and Number Game

Topic link

Train of thought

For some number, NNN, to play the most turns, you take one prime factor at a time until you run out, so the answer is the number of prime factors of NNN. It follows that for n! n! n! The answer is the sum of the prime factors of all numbers 1-n1-sim. So it’s easy to figure out the answer as long as you maintain the prefix sum of the prime factors ahead of time.

How do you find the number of prime factors? For a composite number NNN, suppose there is a smaller composite number MMM and a prime number PPP such that n=m×pn=m\times pn=m×p, then the number of prime factors of NNN can be obtained by adding the number of prime factors of MMM and PPP. This process is the same as euler screening, so that the number of prime factors of the composite number currently screened can be calculated during screening.

code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(u,i) for(int i=head[u]; i; i=e[i].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read(a) {}
void say(a) {}
void say_(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
    int__ =0; _ =0;
    char ch=getchar(a);while(!isdigit(ch))
    {
        if(ch==The '-') __ =1;
        ch=getchar(a); }while(isdigit(ch))
    {
        _=_*10+ch- 48;
        ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
    if(_ <0)
    {
        putchar(The '-'); _ = - _; }if(_ > =10)
       Out(_ /10);
    putchar(_ %10+'0');
}
template <typename T, typename. T2>inline void say(T _, T2... oth)
{
	Out(_).putchar('\n');
	say(oth...) ; }template <typename T, typename. T2>inline void say_(T _, T2... oth)
{
	Out(_).putchar(' ');
	say_(oth...) ; }/ * # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # * /
const ll N=5E6+10;
ll n,l,r;
ll f[N],sum[N],vis[N];
vector<ll> pri;
void sieve(a)
{
	rep(i,2.5E6)
	{
		if(! vis[i]) { pri.emplace_back(i);
			f[i]=1;
		}
		for(auto k:pri)
		{
			if(i*k>5e6)
				break;
			vis[i*k]=1;
			f[i*k]=f[i]+f[k];
			if(i%k==0)
				break; }}}int main(a)
{
	sieve(a);rep(i,2.5e6)
		sum[i]=sum[i- 1]+f[i];
	read(n);
	while(n--)
	{
		read(r,l);
		say(sum[r]-sum[l]); }}Copy the code

Question D of “Tucson Future Cup” National Programming Invitational competition, 2021

Topic link

Train of thought

The original ∏ type I = l1r1i ∣ ∏ I = l2r2i \ prod \ limits_ {I = l_1} ^ {r_1} I/mid/prod/limits_ {I = l_2} ^ {r_2} = l1 ∏ ii r1i ∣ I = l2 ∏ r2i deformation (l2-1)! ⋅ r1! ∣ (l1-1)! ⋅ r2! (l_2-1)! \cdot r_1! \mid (l_1-1)! \cdot r_2! (l2-1)! ⋅ r1! ∣ (l1-1)! ⋅ r2! So it becomes a question of whether factorials are divisible. Set of primes the PPP function fp (x) = yf_p (x) = yfp (x) = y, make py ∣ n, p y + 1 ∤ np ^ y \ mid n, p ^ {y + 1} \ nmid npy ∣ n, p y ∤ n + 1. If and only if for any prime number PPP, fp(n!) Acuity fp (m! f_p(n!) \geq f_p(m!) fp(n!) Acuity fp (m! , n! ∣ m! n! \mid m! n! ∣ m! .

Given p, NP, NP,n, how to find fp(n!)? f_p(n!) fp(n!) ? Because PPP is a prime number, only multiples of PPP contribute to YYY. Each PPP multiple produces 111 contributions, and each p2p^ 2P2 multiple produces 222 contributions, but since PPP multiples overlap with p2p^ 2P2 multiples, p2p^ 2P2 multiples only produce 111 additional contributions, and so on (see Chapter 4 of Concrete Mathematics). ⌊nx⌋\lfloor\frac{n}{x}\rfloor⌊xn⌋, So the fp [n] = ∑ k p 1 ⌊ NPK ⌋ f_p [n] = \ sum \ limits_ {1} k \ geq \ lfloor \ frac {n}} {p ^ k \ rfloorfp [n] = k p 1 ∑ ⌊ PKN ⌋.

code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(u,i) for(int i=head[u]; i; i=e[i].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read(a) {}
void say(a) {}
void say_(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
    int__ =0; _ =0;
    char ch=getchar(a);while(!isdigit(ch))
    {
        if(ch==The '-') __ =1;
        ch=getchar(a); }while(isdigit(ch))
    {
        _=_*10+ch- 48;
        ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
    if(_ <0)
    {
        putchar(The '-'); _ = - _; }if(_ > =10)
       Out(_ /10);
    putchar(_ %10+'0');
}
template <typename T, typename. T2>inline void say(T _, T2... oth)
{
	Out(_).putchar('\n');
	say(oth...) ; }template <typename T, typename. T2>inline void say_(T _, T2... oth)
{
	Out(_).putchar(' ');
	say_(oth...) ; }/ * # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # * /
const ll N=1E7+10;
ll a,b,c,d;
ll vis[N];
vector<ll> pri;
void sieve(a)
{
	rep(i,2.1e7)
	{
		if(! vis[i]) { pri.emplace_back(i);
			vis[i]=1;
		}
		for(auto k:pri)
		{
			if(i*k>1e7)
				break;
			vis[i*k]=1;
			if(i%k==0)
				break; }}}ll fp(ll x,ll p)
{
	return x==0?0:fp(x/p,p)+x/p;
}
void solve(a)
{
	read(a,b,c,d);
	for(auto k:pri)
	{
		ll bc=fp(b,k)+fp(c- 1,k),ad=fp(a- 1,k)+fp(d,k);
		if(bc>ad)
		{
			puts("NO");
			return; }}puts("YES");
}
int main(a)
{
	sieve(a);int _;
	cin>>_;
	while(_ --) {solve();
	}
}
Copy the code