Member Avatar for Blood Night

Crazy notions
Time Limit: 1.0 second
Memory Limit: 1 000 КБ

For five days robot-loader JK546L54p has been buried under the thick layer of the Sibelian plutonium slag. The terrible strike of the atmospheric electricity has led to the depressurization of the robot’s fuel elements. Who will examine this heap of fused, broken metal here, where there is no any robot technician even at distance of a hundred parsecs? Robot-commissar even did not try to investigate what happened with JK546L54p. He ordered to throw him out into dumps and that is all. Nobody noticed that positron brains of JK546L54p were still working. If only the robopsychologist was here with JK546L54p! Of course, he would be killed with the hard gamma radiation in a moment, but… If he attached the visualizer of thoughts to the fused connectors of JK546L54p! He would see the strange performance. Robot was creating! No, I am not joking. He was investigating. Semi casual objects arose in his mind, and he examined them. Crazy properties, crazy theorems.

Besides, here is an example. Let’s take an expression 1n+2n+3n+4n. With how mach zeros ends its decimal notation? JK546L54p solved this problem, and you, student, could you?

Input
In the input there is only one positive integer number n (n <= 300000).

Output
а выходе должно одержать единтвенное чило – чило нулей, на которые оканчивает детична запиь.

Sample Input
Sample input #1
1

Sample input #2
3
Sample Output
Sample output #1
1

Sample output #2
2

  • 4 Contributors
  • 4 Replies
  • 279 Views
  • 3 Weeks Discussion Span
  • Latest Post Latest Post by Fili

Dani AI

Generated

Short answer: the decimal sum S(n)=1^n+2^n+3^n+4^n can end with at most two zeros. Write v2 = exponent of 2 in S and v5 = exponent of 5 in S; the number of trailing zeros is min(v2,v5). One gets a closed, O(1) test for both valuations.

Why v2 is small. For n=1 or any even n, S ≡ 2 (mod 4) so v2(S)=1. For odd n≥3, 2^n and 4^n are divisible by 8 while 3^n ≡ 3 (mod 8), so S ≡ 1+3 ≡ 4 (mod 8) and v2(S)=2. Thus

  • v2 = 1 if n==1 or n is even,
  • v2 = 2 if n is odd and n>1.

Why v5 is simple. By the standard prime-sum fact for p=5, S ≡ 0 (mod 5) whenever 4 ∤ n, and S ≡ −1 (mod 5) when 4 | n. So v5=0 exactly when n ≡ 0 (mod 4). To decide whether 25 divides S, use that 2 and 3 have order 20 modulo 25, so S (mod 25) is 20-periodic. Checking the 20 residues shows S ≡ 0 (mod 25) iff n (mod 20) is one of
{3,5,7,10,11,15,19}.
Hence v5 = 0 if n%4==0, else v5 = 2 for those residues, otherwise v5 = 1.

Combine and take min(v2,v5). Here is a compact C++ implementation:

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    if (!(cin >> n)) return 0;
    int v2 = (n == 1 || (n % 2 == 0)) ? 1 : 2;
    int v5;
    if (n % 4 == 0) v5 = 0;
    else {
        int r = n % 20;
        bool is25 = (r==3||r==5||r==7||r==10||r==11||r==15||r==19);
        v5 = is25 ? 2 : 1;
    }
    cout << min(v2, v5) << '\n';
    return 0;
}

This answers ’s puzzle and shows the problem is trivial to code in C++ (as wondered). Sample checks: n=1 -> 1, n=3 -> 2.

Recommended Answers

All 4 Replies

Member Avatar for Blood Night

hope to find some comrades and communicate sth with ya

Member Avatar for meabed

I Donno .. Is this realted to C++ ??? :?:

Member Avatar for FireNet

I dont know Russian sorry :-))

Member Avatar for Fili

Just asking Blood Night: What does output say?

what does 1n mean 1*n or 1n as a number; what do you mean???
( for all interested my e-mail is -could you send answer here? )

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.