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. 
