The definition of the function f(a, k) has been updated.
Statement of problem G has been clarified, you can recheck it
$a$: is an array of pairs where the first is a prime number and the second is the cost of that prime.
$f(a,k)$ = the minimum cost to write all beautiful numbers less than or equal to k.
A number is beautiful if you can write it as the product of 2 numbers $x$ and $y$ such that $y \geq 1$, and $x > 1$. $x$ is a perfect square made up of primes found in the array $a$. The cost is the sum of costs of the unique primes that make up $x$.
if a number can be made up of multiple combinations of $x$ and $y$ you have to choose exactly one combination to consider when finding the cost of that number.
You are asked to find $f(a,k)$.
The first line is made up of 2 integers $n$,$k$ $(1 \leq n \leq 10^6 , 1 \leq k \leq 10^{12})$.
Each of the next $n$ lines make up the array $a$, each line contains $2$ integers $x_i,$ $y_i$ $(1 < x_i < 10^{12} , 1 \leq y_i \leq 10^6)$, the prime and it's cost, it's guaranteed that $x_i$ is a prime number and there doesn't exist $i,j$ $(i \neq j)$ such that $x_i = x_j$.
Print a single integer, the value of the function.
| Input | Output |
|---|---|
4 10 2 300 3 66 5 100 13 32 Copy
|
666 Copy
|
2 50 3 10 7 21 Copy
|
71 Copy
|
Let's forget about the cost part, for now, the problem becomes a classic problem with a twist.
The classic problem is given a list of primes, find the count of numbers between $1$ and $n$ that are divisible by at least one of those primes, $\sum_{i \epsilon s}^{} (-1)^{|i|}*\frac{n}{i}$, the only difference is the primes are primes^2, this allows us to makes the solution faster than exponential. We want combinations of the squared primes such that their product is between $1$ and $k$, this means their square root is between $1$ and $10^6$. Therefore, instead of trying $2^n$ combinations and overflowing most of the time, it's enough to iterate through the numbers between $1$ and $10^6$ such that all primes in them are raised to the power of $1$ and appear in the input array $a$. Then we can continue with the normal inclusion-exclusion solution. $\sum_{i = 1}^{10^6} (-1)^{|i|}*\frac{n}{i*i}$.
Getting back to the cost part of the problem, the summation becomes .
$$\sum_{i = 1}^{10^6} \max_{p|i} {(cost_{p})} * (-1)^{|i|}*\frac{n}{i*i}$$
Proof:
Let's look at a number x that is made up of y primes, the cost that this number adds to the answer comes from the contribution of 2^y - 1 indices i in the above summation, 2^{y-1} times the value in that summation is positive and 2^{y-1} - 1 times the value is negative. let's sort those y primes by cost in increasing order and let's look at the jth prime, in 2^{j-1} indices i(out of the 2^y - 1 indices), that prime will be the maximum prime(out of all the primes that makes the index i) in terms of cost, half of those indices will have a positive value and the other a negative value(half will have an even amount of primes and half will have odd amount of primes), thus cancelling out and contributing 0 to the answer. The only prime that will contribute non-zero is the prime with the minimum cost since it will only be maximum once with a positive value.
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
int n,p[N],val[N];
long long k,ans;
int main(){
scanf("%d%lld",&n,&k);
for(int i = 0;i < n;i++){
int cost;
long long a;
scanf("%lld%d",&a,&cost);
for(long long j = a;j < N;j+=a){
p[j] = a;
if((j/a)%a == 0)val[j] = 1e8;
val[j] = max(val[j],cost);
}
}
for(int i = 0;i < N;i++){
if(!p[i]){
val[i] = 0;
continue;
}
int cur = i,sign = -1;
while(p[cur])cur/=p[cur],sign*=-1;
if(cur > 1)val[i] = 1e8;
if(val[i] != 1e8)ans+=k/i/i*sign*val[i];
}
printf("%lld\n",ans);
}