DRMP - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Kerim Kochekovich Kochekov
Tester: Joud Zouzou
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Number Theory, Recursion, and pruning.

PROBLEM:

Given an integer M up to 10^{14} Find the number of valid values of A such that A*B is divisible by M and A*B = M*(A+B) for some value of B \geq A

QUICK EXPLANATION

  • By writing B = \frac{A*M}{A-M} and substituting x = A-M, we can find that x divides M^2 for every valid value of A.
  • By writing A*B-M*(A+B) = 0 and adding M^2 both sides, we can see that (A-M)*(B-M) = M^2 which implies x*(y+x) = M, y = B-A \geq 0 since B \geq A. From this, we can find that x cannot exceed \sqrt{M^2} = M.
  • So, we need to find all x such that 1 \leq x \leq M and x divides M^2. This can be done by writing prime factorization of M^2 and recursion to visit each factor exactly once. For every value of x, A = M+x is a valid value of A.

EXPLANATION

Rewriting the equation, we have B = \frac{A*M}{A-M}. Putting x = A-M, we have B = \frac{M*(M+x)}{x}. Hence, M*(M+x) = M^2+M*x should be divisble by x. Since M*x is divisible by x, M^2 should also be divisible by x.

Now, time to go back a bit.

Rewriting the original equation and adding M^2 both sides, we have A*B +M^2 - M*(A+B) = M^2 which is same as (A-M)*(B-M) = M^2 which is x*(y+x) = M^2 with y \geq x since B \geq A. We can see, the maximum valid value of x can be up to \sqrt {M^2} = M.
So, if any x such that 1 \leq x \leq M is the factor of M^2, A = M+x is valid value of A.

Now, this gives us a O(M) time solution by checking all values 1 \leq x \leq M which is sufficient for all but the last subtask.

For the last subtask, we need to do a little more work.

Let’s write the prime factorization of M, we get \prod {p_i}^{k_i} for distinct p_i. It is easy to see that prime factorization of M^2 would be \prod {p_i}^{2*k_i}.

Now, let us define a recursive method which iterates over all factors of a number whose prime factorization is given in array primes (prime, power) pair.

check(0, 1, M) gives all valid factors of $M^2$ which are less than or equal to $M$.
void check(int index, long currentProduct, long maximumLimit ) {
    if(ind==primes.length){
        //currentProduct is valid value.
        ans[count++] = currentProduct;
        return;
    }
    long p = 1;
    for(int i = 0; i<=primes[ind].pow; i++){
       //Check if currentProduct*p > maximumLimit, then break
       if(x>m/p)break;
       //Moving to next prime with choosing ith power of current prime.
       check(ind+1,x*p);
       if(p> m/pr[ind][0])break;
       p*=pr[ind][0];
    }        
}

We can see, that each valid value of x is visited exactly once, so complexity is of the order of O(K) with a constant factor which is sufficient for the final subtask.

For every x \leq M such that x divide M^2, A = M+x is valid value. This solves our problem.

TIME COMPLEXITY

The time complexity is O(K*(C+ log(K))) per test case where K is the number of valid values of A and C is the constant factor.

SOLUTIONS:

Setter's Solution
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
ll N;int sz;
vector<pair<ll,int> >v;
bool bad(ll x,ll y){
	return (x>N/y);
}
vector<ll>ans;
void rec(int pos,ll mul){
	if(pos==sz){
		ans.pb(mul+N);
		return;	
	}
	ll pw=1;
	for(int i=0;i<=v[pos].ss;i++){
		if(bad(mul,pw))
			return;
		rec(pos+1,mul*pw);
		pw*=v[pos].ff;
	}
}	
int main(){
	int t;
	scanf("%d",&t);
	assert(1<=t && t<=10);
	while(t--){
		ll n;
		scanf("%lld",&n);N=n;
		int b=sqrt(n);
		for(int i=2;i<=b;i++)
			if(n%i==0){
				int cnt=0;
				while(n%i==0)
					cnt+=2,n/=i;
				v.pb(mp(i,cnt));			
			}
		if(n!=1)
			v.pb(mp(n,2));	
		sz=v.size();rec(0,1);
		sort(all(ans));
		assert(1<=ans.size() && ans.size()<=int(1e7));
		printf("%d\n",ans.size());
		tr(it,ans)
			printf("%lld\n",*it);
		v.clear();ans.clear();
	}
	return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
	    char g=getchar();
	    if(g=='-'){
	        assert(fi==-1);
	        is_neg=true;
	        continue;
	    }
	    if('0'<=g && g<='9'){
	        x*=10;
	        x+=g-'0';
	        if(cnt==0){
	            fi=g-'0';
	        }
	        cnt++;
	        assert(fi!=0 || cnt==1);
	        assert(fi!=0 || is_neg==false);
 
	        assert(!(cnt>19 || ( cnt==19 && fi>1) ));
	    } else if(g==endd){
	        assert(cnt>0);
	        if(is_neg){
	            x= -x;
	        }
	        assert(l<=x && x<=r);
	        return x;
	    } else {
	        assert(false);
	    }
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
	    char g=getchar();
	    assert(g!=-1);
	    if(g==endd){
	        break;
	    }
	    cnt++;
	    ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
vector<pair<long long,int> > f;
vector<long long> ret;
long long N;
long long M;
void sol(int i,long long val)
{
	if (i==f.size()) // val = (A-M) => A = val+M
	    ret.push_back(val+M);
	else
	{
	    long long cur = val;
	    for (int j=0;j<=f[i].second;j++)
	    {
	        if (cur>M)
	            break;
	        sol(i+1,cur);
	        if (M / cur < f[i].first)break;
	        cur*=f[i].first;
	    }
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
	    ret.clear();
	    f.clear();
	    cin>>M;
	    long long X = M;
	    for (long long i=2;i*i<=X;i++)
	    {
	        int cur=0;
	        while(X%i==0)
	        {
	            X/=i;
	            cur++;
	        }
	        if (cur>0)
	            f.push_back({i,2*cur});
	    }
	    if (X>1)f.push_back({X,2});
	    sol(0,1);
	    sort(ret.begin(),ret.end());
	    printf("%d\n",(int)ret.size());
	    for (auto x:ret)printf("%lld\n",x);
	}
	//assert(getchar()==-1);
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
	//SOLUTION BEGIN
	//This code is not meant for understanding, proceed with caution
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    long m = nl(), x = m;
	    long[][] pr = new long[30][];int cnt = 0;
	    for(long i = 2; i*i<= m; i++){
	        if(x%i!=0)continue;
	        int c = 0;
	        while(x%i==0){x/=i;c++;}
	        pr[cnt++] = new long[]{i,c};
	    }
	    if(x>1)pr[cnt++] = new long[]{x,1};
	    count = 0;
	    check(pr, cnt-1, 1, m);
	    pn(count);
	    Arrays.sort(ans, 0, count);
	    for(int i = 0; i< count; i++)pn(m+ans[i]);
	}
	long[] ans = new long[(int)2e7];
	int count = 0;
	void check(long[][] pr, int ind, long x, long m){
	    if(ind==-1){
	        ans[count++] = x;
	        return;
	    }
	    long p = 1;
	    for(int i = 0; i<=2*pr[ind][1]; i++){
	        if(x>m/p)break;
	        check(pr, ind-1,x*p,m);
	        if(p> m/pr[ind][0])break;
	        p*=pr[ind][0];
	    }
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	long mod = (long)1e9+7, IINF = (long)1e18;
	final int INF = (int)1e9, MX = (int)1e6+1;
	DecimalFormat df = new DecimalFormat("0.0000000");
	double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
	static boolean multipleTC = true, memory = false;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    int T = (multipleTC)?ni():1;
//        Solution Credits: Taranpreet Singh
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
	    else new Main().run();
	}
	long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
	int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}   

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

4 Likes

This explanation can be simplified: Firstly since B must be positive, and we have B = \frac{A*M}{A-M}, we require A - M \ge 1. So x \ge 1.

And since B \ge A, we have \frac{M*(M+x)}{x} \ge (M+x). So, we get \frac{M}{x} \ge 1.
=> x \le M.

So, 1 \le x \le M.

5 Likes

My approach is a little different:

The question boils down to finding all divisors of M^2 less than M

as B can be represented as B = M + (M^2/i)
( where A = M+i and 1 \leq i \leq M )
So for B to be a positive integer, i must be a divisor of M^2 (otherwise (M^2/i) won’t be an integer)

We use the fact that:
All\ divisors\ of\ M^2\ can\ be\ split\ into\ 2\ divsors\ of\ M

This can be seen/proven using the following example:
Let the prime factorization of M be as follows: M = ( 2*2*3*5*23*23 )
Any combination of numbers in factorization is a divisor of M
We can write prime factorization of
M^2\ as\ M^2 = M * M = ( 2*2*3*5*23*23 ) * ( 2*2*3*5*23*23 )
Here, prime factorization is shown as being split into 2 sets which are prime factorization of M.
A divisor of M^2 can be represented as a combination of numbers in factorization of M^2, and it is easy to see that it can be split in 2 values each in one set(out of the 2 shown) respectively, i.e. they are divisors of M
Eg: prime factorization for divisor 48668 = ( 2*2*23 ) * ( 23*23 ) = 92 * 529 both of which are divisors of M
This fact can be extended for any positive integer M

Using this fact, all we need to do is :

Find divisors of M^2 by multiplying all divisors of M with each other

First, find all divisors of M and put them in a list ( can be done in O(sqrt(M)) - link ) )
let us denote number of divisors of M as n_d
upper bound for the number of divisors can be assumed as O(n^{1/3}) - link )

Second, multiply each divisor with all other divisors(including itself) and include it in the list if it is less than M
second process can be made easier if the list is sorted
time complexity of second process is O((n_d)^2) but we prune the iteration if value of multiplication of 2 divisors is more than M and list is sorted(check for int overflow too), so time complexity is lower than this.
We also need to remove duplicate values in the list after this operation

Print the answer as (M + i) for all values i in the list of divisors

Submission link : https://www.codechef.com/viewsolution/24107364

Please inform if any mistakes are found

P.S. : please do not add unnecessary details in problem statement and that too such a big story. First paragraph could have been skipped from problem statement.

3 Likes

I personally feel the statement was not that long. You don’t always get 5 line statements. It’d had been problematic if it’d had been two-three chunks of story. I don’t recall last years ICPC (at least online qualifiers) being 5 line statements.

So I’d rather suggest that you try to adapt to statements with >100 words rather than asking the world to tone it down.

4 Likes

Yes. I actually approached it that way, so explained that. :sweat_smile:

Can anyone help me understanding this base case

This means, that we have considered some powers of all primes, and currentProduct is the value we have got in our branch.

1 Like