# GUESSNUM Editorial

Tester: Roman Bilyi
Editorialist: Hussain Kara Fallah

### PROBLEM EXPLANATION

Chef is playing a game with his brother Chefu. He asked Chefu to choose a positive integer N, multiply it by a given integer A, then choose a divisor of N (possibly N itself) and add it to the product. Let’s denote the resulting integer by M; more formally, M=A⋅N+d, where d is some divisor of N.

Chefu told Chef the value of M and now, Chef should guess N. Help him find all values of N which Chefu could have chosen.

Easy

### CONSTRAINTS

1 \leq M \leq 10^{10}

### EXPLANATION:

Initially, we know that:
M=A*N+D
But D is a divisor of N so N=Q*D So:
M=A*Q*D+D
M=D*(A*Q+1)
So we know that D must be a divisor of M also.
Let’s check all divisors of M, this can be done in O(\sqrt{N}) complexity
For each divisor d let’s find R=\frac{M}{d}-1
Now if R is divisible by A then we have q=\frac{R}{A} and we have a potential candidate of N which is q*d. After finding all candidates just sort them and remove duplicates and output the values. Also, just make sure you don’t consider 0 as a possible answer.

Editorialist solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
long long A, M;
cin >> A >> M;
set<long long> ans, div;
for (long long j = 1; j * j <= M; j++) {
if (M % j == 0) {
div.insert(j);
div.insert(M / j);
}
}
for (auto D : div   ) {
long long q, rem = M / D;
rem--;
if (rem % A) continue;
q = rem / A;
ans.insert(q * D);
}
ans.erase(0);
cout<<ans.size()<<endl;
for(auto pp : ans)
cout<<pp<<' ';
cout<<endl;
}

}

Tester Solution
	#include "bits/stdc++.h"
#include <chrono>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 200007;

const int MOD = 1000000007;

const double Pi = acos(-1.0);

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){
}
long long readIntLn(long long l,long long r){
}
string readStringLn(int l,int r){
}
string readStringSp(int l,int r){
}
void eof() {
string trash;
assert(!(cin >> trash));
}

Int F(Int M, Int A, Int d)
{
if (d >= M) return -1;
M -= d;
if (M % A != 0) return -1;
M /= A;
if (M % d != 0) return -1;
return M;
}

int main(int argc, char* argv[])
{
ios::sync_with_stdio(false); cin.tie(0);
srand(time(0));

int t = readIntLn(1, 100);
FOR(tt,0,t)
{
int A = readIntSp(1, 1000000);
Int M = readIntLn(1, 10000000000LL);
assert(A < M);
vector<Int> res;
for(Int i = 1; i * i <= M; i++)
if (M % i == 0)
{
Int x = F(M, A, i);
Int y = F(M, A, M / i);
if (x != -1)
res.push_back(x);
if (y != x && y != -1)
res.push_back(y);
}
sort(ALL(res));
cout << SZ(res) << endl;
FOR(i,0,SZ(res))
{
cout << res[i] << ' ';
}
cout << endl;
}

eof();

cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}

4 Likes

What is this statement for?

1 Like

https://www.codechef.com/viewsolution/28592030
Can any one help me understand why I am getting RE (NZEC) for this solution?

even with this its not passing original constraints !!?.. what to do !?
PS: i used the same approach and code is almost similar too as that of editorialist

The “almost” similar code has a bug then.

2 Likes

https://www.codechef.com/viewsolution/28585953
plz help in finding bug in my code

Sorry, I don’t know JAVA that well, I code in C++

long a = s.nextInt();
long m = s.nextInt();

m <= 10^10 and a<m

Use long for storing A and M

We are storing all the factors of M in set div. If j is a factor of M that means M/j is a factor too. Hence, inserting both j and M/j in div.

@ankit_2305 its still not passing original constraints

                for (long f : arrLL){
if ((f-1)%a == 0){
long q = (f-1)/(int)a;
**long d = (int)m/f;**
long n = q*d;
if (n != 0 ){
count ++;
}
}
}


@raksha1906
It is a similar mistake, typecasting long m to int will alter the value of m for values lying outside the range of integer which will result in unexpected output.
You may replace
long d = (int)m/f;
with
long d = m/f;

1 Like

it got solved … thanks

while (t–>0) {

		long a = s.nextLong();
long m = s.nextLong();
ArrayList<Long>mr= new ArrayList<>();
long k =(long) Math.floor(Math.sqrt(m));
for (int j = 1; j <=k; j++) {
if (m%j==0){
long r = m/j;
if ((j-1)%a==0){
}
if(	r!=j){                  // THIS BLOCK
if ((r-1)%a==0){
}
}
}
}
System.out.println(mr);

}


hey can you also explain me what the second if block is doing ?

this is for …
since q = (j-1)/a … and q is an integer, so j-1 should be completely divisible a…
so (j-1)%a == 0 helpes in checking whether this condition is satisfied or not … and only accepts those values of q which satisfies the condition

yes that’s the first if block what about this one ?? i wasn’t able to come up with this condition

My solution is little bit different .it is able to pass 50 % but next its showing TLE. can anyone please help https://www.codechef.com/viewsolution/28610451

Here j is a factor of M as it satisfies (M%j==0) and we store a corresponding value of N in mr [Explained in editorial]
Coming to the second block, we have r = M/j where j is a factor of M which means r is a factor too eg. 5 is a factor of 10 and 10/5 = 2 is a factor of 10. So we have to add the corresponding value of N in mr for r but if r is same as j we will get repeating values of N so we put condition if(r!=j)

1 Like

Your approach is taking O(N) time.

Hi I just used use the approach:
for i = a%m to i<=m and incrementing i = i + a:
so now if((m-a)/a)%i == 0 && i != 0)
we can insert into some vector…

But this approach is giving me WA Ik it should give some TLE but why WA?