 # EGRCAKE - Editorial

Author: Egor Bobyk
Tester: Istvan Nagy
Editorialist: Xellos

SIMPLE

### PREREQUISITES:

Greatest common divisor.

### PROBLEM:

We have a permutation \texttt{P}[0..N-1] with \texttt{P}[x]=M+x for x < N-M and \texttt{P}[x]=x-(N-M) for x \ge N-M. Start at x=0 and keep moving from x to \texttt{P}[x]. When visiting some x for the second time, stop. How many different x-s have been visited?

### QUICK EXPLANATION:

The number of robots with cakes is N/gcd(N,M), which can be found using Euclid’s GCD algorithm.

### EXPLANATION:

For permutations, it’s a well-known fact that if we start at x=0, we’ll stop at x=0 as well - a permutation is made of cycles.

We can just simulate the first subtask. For the second subtask, this is too slow, but we can reduce our problem to a completely different one. The trick is to see that in each step, we’re sent from x to x+M and if we see that x \ge N afterwards (it really happens iff x \ge N-M before this step), then we subtract N to get it back into the range [0,N). Imagine what’d happen if we wrote the permutation on paper and connected its ends - we’re always just moving M places to the right on the tape. More formally, after moving to the next robot j times, we have x=(jM)\% N.

When will we visit x=0 again, then? It happens for the smallest positive j such that N\,|\,jM; which is known to be N/gcd(N,M) (think why). That’s the answer to the question “how many robots will have a cake at the end?”; if it’s N - if N and M are coprime - we should print “YES”.

The greatest common divisor can be computed using Euclid’s algorithm in O(\log N), which is the time complexity per test case. Memory: O(1).

### AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.
The tester’s solution can be found here.
The editorialist’s solution can be found here.

### RELATED PROBLEMS:

2 Likes

could you please explain why its n/gcd(n,m), i didn’t get that.

what is wrong with my code.
I think of this problem as cyclic figure e.g 8, 2 (n, m)

``````    3(start)
2       4
1       5
``````

``````8       6
7

#include <stdio.h>

int main()
{
int t;
scanf("%d", &t);
while(t--) {
int n, m;
scanf("%d%d", &n, &m);
if(m==0) {
if(n==1)
printf("Yes\n");
else
printf("No 1\n");
continue;
}
if((n-m)%m==1)
printf("Yes\n");
else
printf("No %d\n", ((n-m)/m) + 1);
}
return 0;
}
Just think of we need to determine whether n-m is completely divisible by m or not, if remainder is 1 the print (n-m)/m else print yes(as if it would be greater than 1 or 0), it would surpass 1 and repeats until it gets to one, thereby filling all 2 to m. try some other cases.``````

Any idea why this approach fails? @Xellos? It passes all except 4 testcases

I tried a different approach to this problem. Here’s what I did:

I precomputed the lowest prime number for every number less then the max limit of M as given in the question. Now, If you notice, (atleast this worked out for small values), we can prime factorize M and if any of it’s prime factor is divisible by N, we divide N by that prime factor ONCE and continue factorizing M.< br>
In the end, if N does not change, that means that the answer is ‘YES’ else the answer is ‘NO’ followed by the current value of N which had been divided in the middle

Here’s my code which explains it more clearly:

https://www.codechef.com/viewsolution/8772878

P.S: I came across the GCD logic hours later What does N|jM mean ??

1 Like

What is wrong with my code? Why is it necessary to use gcd?
#include
#include
using namespace std;

int main()
{
int t, n, m, i, k;

``````cin>>t;
while(t--)
{
cin>>n>>m;
pair <int,int> p[n];
for(i=0; i<n-m; i++)
p[i].first=m+i+1;
for(i=n-m; i<n; i++)
p[i].first=i-n+m+1;

p.second=1;
for(i=1; i<n; i++)
p[i].second=0;
k=p.first-1;
while(1)
{
k++;
if(p[k-1].second==1)
break;
else
{
p[k-1].second=1;
k=p[k-1].first-1;
}

}
int count=0;

for(i=0; i<n; i++)
if(p[i].second==0)
count++;
if(count==0)
cout<<"Yes"<<endl;
else
cout<<"No "<<count<<endl;

}
``````

}

#include <stdio.h>
#include <stdlib.h>
int main(){
long int a,b,c;
int t;
scanf("%d",&t);
while(t–){
int m,n,i,j;
scanf("%d",&n);
scanf("%d",&m);
for(i=1;i<=n;i++){
a[i]=i;
}
j=1;
for(i=m+1;i<=n;i++){
c[j]=a[i];j++;
}
for(i=1;i<=m;i++){
c[j]=a[i];j++;
}
for(i=1;i<=n;i++){b[i]=0;}
b[c]=1;
i=1;
while(b[i]!=1){
b[c[i]]=1;
i=c[i];
}
for(i=1;i<=n;i++){
if(b[i]==0){printf(“no”);}
else{printf(“yes”);}
}
}
return 0;

}
whats wron with my ans.

@Xellos0

When will we visit x=0,x=0 again, then? It happens for the smallest positive j such that N|jM; which is known to be N/gcd(N,M).

can someone please explain why the smallest value of J is N/gcd(N,M)?

Which part did you not get? You’re basically always moving M places to the right and looking for the first time when you’ve moved by a multiple of N places in total.

Try it for N=3, M=1. You say the answer is NO, but it’s YES.

It seems you don’t know what GCD is.

got it now thanks btw

N divides j*M

help me…somebody

10**9 array? Insufficient memory

as leaving the array part