Hello! This is the roadrice field of a master's student in bioinformatics! It's been a while since I died from the last time, but since I participated in ABC169, please write down the entry.
Multiplication up to 3 digits is learned by the third grade of elementary school in the current course of study.
My answer
A.py
A,B = map(int, input().split())
print(A*B)
I implemented it exactly as it was written once.
B.py
N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(N):
ans *= A[i]
if ans <= 1e18: print(ans)
else: print(-1)
The result is TLE
. The numbers are big, right?
If there is 0 in the input, the answer is 0 at that moment, so if it is judged whether there is 0 in the input first, 0
is output without multiplication and the process ends, 10 18 during the calculation. If it exceeds </ sup>, I thought that it would be faster if I break there and output -1
, so I wrote as follows.
B.py
N = int(input())
A = list(map(int, input().split()))
ans = 1
flg = True
if 0 in A: print(0)
else:
for i in range(N):
ans *= A[i]
if ans > 1e18:
flg = False
break
if flg: print(ans)
else: print(-1)
By the way, this reduced the calculation time from the maximum 2206 ms
to 56 ms
. It will be considerably faster with a little ingenuity.
I knew it was about floating point, but it didn't work out ... I didn't study enough information technology ...
I used C ++ for this problem. You can maximize the number of operations by doing the following:
First, factor the given * N * into prime factors.
N = a^{6} \times b^{4} \times c^{3}
Let z = a 1 </ sup>. Replace N with N / z. You can't choose the same z, so next is a 1 </ sup>, which is the next smallest a 2 < Select / sup> for z. Replace N with N / z.
N = a^{3} \times b^{4} \times c^{3}
It still splits at z = a 3 </ sup>. Replace N with N / z.
N = b^{4} \times c^{3}
Next, divide by z = b 1 </ sup> ...
Repeatedly dividing the prime factors by the 1st, 2nd, and 3rd powers, and if the prime factors are exhausted in * N *, divide by the 1st, 2nd, and 3rd powers of the next prime factors. You just have to repeat the process.
My answer
D.cpp
#include<bits/stdc++.h>
using namespace std;
vector<long long> pri_fac(long long N){
vector<long long> yakusu;
long long now = 0;
long long a = 2;
while(N >= a*a){
if(N%a == 0){
yakusu.push_back(a);
N /= a;
}else{
a++;
}
}
if(N != 1) yakusu.push_back(N);
return yakusu;
}
int main(){
long long N;
cin >> N;
vector<long long> vec_all;
vec_all = pri_fac(N);
if(N == 1) cout << 0 << endl;
else if(vec_all.size() == 1) cout << 1 << endl;
else{
long long now;
now = vec_all[0];
vector<long long> unique_count;
unique_count.push_back(1);
for(long long i=1;i<vec_all.size();i++){
if(vec_all[i] != now) unique_count.push_back(1);
else unique_count[unique_count.size()-1]++;
now = vec_all[i];
}
long long ans = 0;
for(long long i=0;i<unique_count.size();i++){
long long j = 1;
while(j <= unique_count[i]){
ans++;
unique_count[i] -= j;
j++;
}
}
cout << ans << endl;
}
return 0;
}
When * N * is 1 or a prime number, I didn't want a bug, so I'm doing exception handling first. Pri_fac
is a function that performs prime factorization and pushes the prime factors to vector.
Recommended Posts