C - Repsept (Atcoder ABC 174)

1

Problem : C - Repsept

This is a question from Atcoder ABC 174.

Can someone explain why the answer doesn’t exist only for the numbers that are multiples of 5 and 2.(Why the answer will always exist for other numbers ?)

And why the answer will be less than equal to the “k” ?

2

@im_skp
multiples of 5 always ends with 5 or 0 but in the given pattern that is 7, 77, 777, 7777, …
all the numbers ends with 7 thus none of the number ends with 5 or 0 so there will not be any multiple of 5
similar goes for 2, the multiple of 2 ends with 0, 2, 4, 6, 8 but in the given pattern none of the number ends with 0, 2, 4, 6, 8 that’s why none of the number in the given pattern can be a multiple of 5 or 2

2 Likes
3

Understood but i want to know what’s the proof that the answer will always exist for any other number say (11 or 13) which are not the multiples of 2 or 5.

4

I could never understand this.
It was disappointing problem in totality.

5

There is,no guarantee that it will exist. 2 and 5 are the base cases

1 Like
6 
void solve1()
{
    int n;cin>>n;
    int c=0,ans=0;
    for(int i=0;i<10000000;i++)
    {
        c+=7;
        c%=n;c*=10;
        ans++;
        if(c==0)
        {
            break;
        }
    }
    if(c==0)cout<<ans<<endl;
    else cout<<-1<<endl;
}

You need not prove to solve this question, just do big integer division to get ac

7

@rahulmysuru7 could you please explain the solution, you have posted.

8

It doesn’t exist for 5 and 2 because we use base 10.

9

n%k will always be less than k and >=0. So if you tried k times and haven’t found 0 as remainder then you will find a remainder that you had already gotten before and hence it will be a loop. So after k+1 tries, You can print -1 as it won’t be divisible.
For divisibility by 2, these last digit of the number must be even. Here it’s 7. So answer is -1 for any even number.
For div by 5 last digit is always 0 or 5. So, answer is -1.
You don’t need these separate div-by-2 or by-5 cases. Just a single implementation till k+1 tries is enough.
Here’s my code: Submission #15649567 - AtCoder Beginner Contest 174

3 Likes
10

same explanation as what waltzer told below.

1 Like