PROBLEM LINK:
Author: Adarsh Agrawal
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia
DIFFICULTY:
Medium
PREREQUISITES:
Number Theory, Pigeonhole Principle, Prime Sieve, Binary Exponentiation.
PROBLEM:
Consider an arithmetic progression of N terms and a common difference of K. Let X be the product of its elements. Find the highest number which divides X, irrespective of the choice of the initial term of the sequence, A.
HINTS:
Not the full solution. Just some hints to help you if you are stuck at some point. As soon as you encounter a hint that you had not thought of, go back to solving the problem.
Hint 1:
Can you solve the problem when K=1?
Hint 2:
On multiplying any sequence of N consecutive numbers, how many times does a prime factor p appear in this product, i.e., what is the highest power p^k, such that the product modulo p^k=0, but it does not equal to 0 on modulo p^{k+1}?
Hint 3:
p can’t be equal to K. In fact, p can’t divide K.
As an example, take the sequence:
1, 1+2*K, 1+3*K, \ldots
If p divides K,
K mod p = 0.
\implies every term of the above sequence mod p = 1.
\implies p won’t be a part of the answer if p divides K.
Hint 4:
What if the numbers in the sequence aren’t consecutive (common difference of 1), but have a common difference of K?
Take any number p, such that 1<p<K and K mod p \not=0.
Take any arithmetic progression with a common difference of K, and starting number 1. Try to take a sequence of length at least 3*p. It will be of the form (1, 1+K, 1+2*K, 1+3*K, \ldots).
Create a new sequence, formed from every term in the above sequence modulo p.
What do you observe?
QUICK EXPLANATION:
show
Let p be a part (prime divisor) of the answer. p can’t divide K and p \leq N. p will appear (\lfloor \frac{N}{p} \rfloor + \lfloor \frac{N}{p^2} \rfloor+ \lfloor \frac{N}{p^3} \rfloor + \ldots \lfloor \frac{N}{p^k} \rfloor), p^k \leq N and p^{k+1}>N, in the answer, so, find all prime numbers p which do not divide K, raise them to the power of (\lfloor \frac{N}{p} \rfloor + \lfloor \frac{N}{p^2} \rfloor+ \lfloor \frac{N}{p^3} \rfloor + \ldots\lfloor \frac{N}{p^k} \rfloor) and multiply them, to get the answer.
EXPLANATION
show
Let’s first solve the problem for K = 1, i.e., the numbers have a common difference of 1. Thus, the problem we now have is : What is the highest number that divides the product of any N consecutive numbers?
Take any N or more consecutive numbers. At least one of them will be divisible by N. \dots (1)
why
This comes from the pigeonhole principle, which states that when we have N containers and we need to distribute more than N objects among them, at least 1 container will contain more than 1 object.
Consider the sequence:
A_1, A_2, A_3, \ldots, A_N
When we divide the numbers of the sequence by N, the possible remainders can be:
0, 1, 2, 3, \ldots, N-1, i.e., N possible remainders.
Also, as the numbers are consecutive,
A_{i+1} (mod N) \equiv (A_i+1) (mod N)
If none of the numbers are divisible by N, none of them will give the remainder 0, on dividing by N.
\implies that at least 2 numbers will give the same remainder upon dividing by N.
Let the numbers be A_i and A_j, (A_i<A_j).
A_i (mod N) \equiv A_j (mod N).
\implies A_j - A_i (mod N) \equiv 0 (mod N)
This is only possible if the numbers differ by N or more, as modulo cycles on consecutive numbers (modulo N) only repeat after N terms.
But, in our sequence above, the highest and the lowest numbers differ, at max, by N-1. This is a contradiction. Thus, out of the N consecutive numbers, at least one of them will give 0 modulo N.
\therefore Every N consecutive numbers has a number divisible by N.
Every number >1 is made up of one or more prime numbers. When we take a prime number of a certain power (power \geq 0) and multiply it with other primes numbers of certain powers (power \geq 0), we can form any number.
For example,
6 = 2^1*3^1
63 = 3^2*7^1
Our answer too will have a unique combination of prime numbers raised to their respective powers. Since we need to maximise the answer, we need to find a valid combination which produces the maximum result.
Let p be a prime divisor of the answer. If N \geq p, then, from (1), at least one number in the sequence will be divisible by p. In fact, from the pigeonhole principle, at least \lfloor \frac{N}{p} \rfloor numbers will be divisible by p in any sequence of N numbers. Thus, p will appear in the answer at least \lfloor \frac{N}{p} \rfloor times. If N is less than p, there will exist atleast one sequence of consecutive numbers which doesn’t contain even a single number divisible by p.
But, what if p^2 is also \leq N? Multiples of p^2 have p twice inside the same number, but we have counted p only once for every multiple of p in \lfloor \frac{N}{p} \rfloor. So, p will appear in the answer \lfloor \frac{N}{p} \rfloor (Wherever p appears once) + \lfloor \frac{N}{p^2} \rfloor (wherever p appears once more) times.
But, what if p^3 is also \leq N? p^4 \leq N? and so on?
Thus, to find how many times a prime factor p will appear in the answer, we need to find:
\lfloor\frac{N}{p}\rfloor + \lfloor \frac{N}{p^2} \rfloor+ \lfloor \frac{N}{p^3} \rfloor + \ldots \lfloor \frac{N}{p^k} \rfloor, where,
p^k \leq N and p^{k+1}>N, i.e., k is the highest power of this prime number, such that when we raise this prime number p to the power of k, the resulting number remains \leq N.
p raised to this sum will amount to the power of p in the answer.
From (1), every number 1 \leq x \leq N will appear at least once in the answer. And as the answer is made up of prime numbers (just like every other number), we can find all primes \leq N, raise them to the power (\lfloor\frac{N}{p}\rfloor + \lfloor \frac{N}{p^2} \rfloor+ \lfloor \frac{N}{p^3} \rfloor + \ldots \lfloor \frac{N}{p^k} \rfloor) and multiply them to get the answer.
As N can be as big as 10^6, we can find all primes \leq N efficiently using Sieve of Eratosthenes.
An efficient way to perform the exponentiation can be found here.
Thus, we have solved the problem for consecutive numbers, i.e., K=1. Let’s now see how we can solve the problem for higher values of K too.
1 divides every number. Thus, our answer will at least be 1, for any N and K.
Let’s see what happens if K=10, and we start the sequence from 1.
1, 11, 21, 31,41, \ldots
We see that none of the numbers in the sequence are divisible by 10. None of the numbers in the sequence are divisible by any factor (>1) of 10. In fact, at least one sequence will always exist in which none of the numbers are divisible by any factor of K. And since at least once such sequence exists, neither K, nor any of its factors (>1) can be a part of the answer.
why does this happen?
Consider any sequence:
A_1, A_1+K, A_1+2*K, A_1+3*K,\ldots,
where A_1 mod K \not \equiv 0, i.e., A_1 does not divide K.
Let A_1 mod K \equiv x, (x \not = 0)
\implies (A_1+K) mod K will also be \equiv x
and so will every other term in the sequence.
Since none of the terms in the sequence produced 0 modulo K, hence none of them will be divisible by K.
Let’s now consider a factor of K, f, (1<f<K).
Let the terms of the sequence be of the form (A_1+x*K).
As we just need to find a single A_1, whose sequence will have no numbers divisible by any factor (>1) of K, let’s take A_1=1
As f divides K,
(1+x*K) mod f \equiv ((1 mod f)+(x*K mod f))(mod f) \equiv ((1 mod f) + (0 mod f)) (mod f) \equiv 1.
As we have taken a factor greater than 1, thus none of the terms in the sequence will be divisible by any factor of K.
We will use this observation, along with our solution for K=1 to solve the problem.
Consider the following sequence, with K=9:
5, 14, 23, 32, 41, 50, 59, 68, 77, 86, 95, \ldots
Let’s consider 7 as a possible prime factor of the answer (7 does not divide 9).
The numbers give the following sequence, modulo 7:
5, 0, 2, 4, 6, 1, 3, 5, 0, 2, 4, \ldots
i.e., it will have all numbers from 0 to 6, (notice 6=7-1),
and this modulo sequence will cycle after every 7 terms.
Take any sequence with any K, and try the above with any p which does not divide K. The modulo sequence will always have every number from 0 to p-1, and will cycle after p terms, i.e., will have a periodicity of p.
As there are N terms, from 0 to p-1, which cycle every p terms,
it is same as taking a sequence of N consecutive numbers modulo p.
\therefore p will appear in this result (\lfloor\frac{N}{p}\rfloor + \lfloor \frac{N}{p^2} \rfloor+ \lfloor \frac{N}{p^3} \rfloor + \ldots \lfloor \frac{N}{p^k} \rfloor) times, p^k \leq N and p^{k+1}>N. Thus, raising p to this power will give the us the contribution of p in the answer.
Thus, instead of considering all prime numbers \leq N as parts of the answer, we’ll only take the primes which do not divide K.
Thus, to solve the problem,
- Find all prime numbers \leq N, which do not divide K
- Raise them to the power (\lfloor\frac{N}{p}\rfloor + \lfloor \frac{N}{p^2} \rfloor+ \lfloor \frac{N}{p^3} \rfloor + \ldots \lfloor \frac{N}{p^k} \rfloor) , p^k \leq N and p^{k+1}>N.
- Multiply them, modulo (10^9+7).
SOLUTIONS:
Setter
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define U 998244353
#define N 1000005
#define int long long
#define sz(c) (int)c.size()
#define fr first
#define ll long long
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define r0 return 0;
#define endl '\n'
#define INF (int)1e15
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
bool prime[N];
void seive()
{
memset(prime, true, sizeof(prime));
prime[1] = false;
for (int p=2; p*p<=N; p++)
{
if (prime[p] == true)
{
for (int i=p*p; i<=N; i += p)
prime[i] = false;
}
}
}
int power(int x, unsigned int y, unsigned int m)
{
if (y == 0)
return 1;
int p = power(x, y/2, m) % m;
p = (p * p) % m;
return (y%2 == 0)? p : (x * p) % m;
}
signed main()
{
ios_base::sync_with_stdio(0);
int TESTS=1;
seive();
cin>>TESTS;
while(TESTS--)
{
int n,k;
cin >> n >> k;
int ans = 1;
for(int i=1; i<=n; i++){
if(prime[i] && k%i){
int temp = n;
while(temp/i){
ans = (ans*power(i,temp/i,M))%M;
temp /= i;
}
}
}
cout<<ans << endl;
}
}
Tester
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
int power(int a,int b){
int res=1;
while(b>0){
if(b%2){
res*=a;
res%=mod;
}
a*=a;
a%=mod;
b/=2;
}
return res;
}
const int N=1e6+6;
int c[N];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t,i,j;
cin>>t;
//t=1;
for(i=2;i*i<N;i++){
if(c[i]){
continue;
}
for(j=i*i;j<N;j+=i){
c[j]=1;
}
}
while(t--){
int n,k,ans,p,s;
cin>>n>>k;
ans=1;
for(i=2;i<=n;i++){
if(c[i]==0&&k%i!=0){
p=i;
s=0;
while(n>=p){
s+=n/p;
p*=i;
}
ans*=power(i,s);
ans%=mod;
}
}
cout<<ans<<endl;
}
return 0;
}
Editorialist
CodeChef: Practical coding for everyone
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
private static boolean isPrime[];
private static final int lim=(int)(1e6+5);
private static final long MOD=(long)(1e9+7);
private static void sieve(int N) //sieve of eratosthenes
{
Arrays.fill(isPrime,true);
isPrime[0]=isPrime[1]=false;
for(int i=2;i*i<=N;i++)
{
if(isPrime[i])
for(int j=i*i;j<=N;j+=i)
isPrime[j]=false;
}
}
private static long pow(long a, long b) //binary exponentiation
{
a%=MOD;
b%=(MOD-1); //only if MOD is prime
long res=1;
while (b>0)
{
if((b&1)==1)
res=(res*a)%MOD;
b>>=1;
a=(a*a)%MOD;
}
return res%MOD;
}
public static void main(String[] args) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int i,N;
isPrime=new boolean[lim+5];
sieve(lim);
ArrayList<Integer> primes=new ArrayList<>();
for(i=2;i<isPrime.length;i++) if(isPrime[i])primes.add(i);
int T=Integer.parseInt(br.readLine().trim());
StringBuilder sb=new StringBuilder();
while(T-->0)
{
String s[]=br.readLine().trim().split(" ");
N=Integer.parseInt(s[0]);
long K=Long.parseLong(s[1]);
long ans=1;
for(int p:primes) //prime numbers
{
if(p>N) break;
if(K%p==0) continue; //p should not divide K
int count=0;
for(long curP=p;curP<=N;curP*=p) //contribution of powers of p
count+=N/curP;
ans=(ans*pow(p,count))%MOD;
}
sb.append(ans).append("\n");
}
System.out.println(sb);
}
}
Feel free to share your approach if it differs. You can ask your doubts below. Please let me know if something’s unclear. I would LOVE to hear suggestions 