PROBLEM LINK:
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.
DIFFICULTY:
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){
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,' ');
}
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;
}
Ik it should give some TLE but why WA?