After I came up with a solution, I tried to do it without organizing it, so it took a long time to implement extra to solve the D problem. I want to keep in mind ** implementation after I finish organizing and see the path **.
Outputs YES if the input is 3, 5 or 7.
answerA.py
x=int(input())
print("YES" if x==3 or x==5 or x==7 else "NO")
The character string S is examined in order from the front, and the smallest absolute value of the difference from 753 is output.
answerB.py
s=input()
l=len(s)
ans=[]
for i in range(l-3+1):
ans.append(abs(int(s[i:i+3])-753))
print(min(ans))
In such a problem, ** counting using a recursive function ** and O (the number of 753 numbers). However, I wanted to do it in a different way to skip the implementation of the recursive function, so I thought of a different way to count all the possible numbers and find it in a binary search.
Specifically, the 753 number is `[" 3 "," 5 "," 7 "]`
, which is the direct product of the ** array ** (** the product function of itertools is convenient **, so please remember it. Let's keep it in mind.) Of the numbers combined as a character string without changing the order, 3 and 5 and 7 appear at least once, so I put all such numbers in the ans array. Then, I sorted the ans array in ascending order and searched for how many elements ** n or less by binary search **. (The last part of the output is wasteful because I had a bug in my head. If I fix the waste, it will look like a comment out.)
Also, it is okay to avoid recursive functions, but without a binary search **, when searching for the first 753 number candidates, just count whether it is n or less and the answer can be obtained immediately **. I noticed. The improved version is the third code.
answerC.py
from itertools import product
n=int(input())
ans=[]
for i in range(3,10):
l=list(product(["3","5","7"],repeat=i))
for j in l:
if len(set(j))==3:
ans.append(int("".join(list(j))))
ans.sort()
m=len(ans)
l,r=0,m-1
while l+1<r:
k=(l+r)//2
if ans[k]<n:
l=k
elif ans[k]>n:
r=k
else:
l,r=k,k
break
if ans[l]==n:
print(l+1)
elif ans[r]==n:
print(r+1)
elif ans[l]>n:
print(l)
elif ans[r]<n:
print(r+1)
elif ans[l]<n:
print(l+1)
'''
if ans[l]>n:
print(l)
elif ans[r]<=n:
print(r+1)
else:
print(l+1)
'''
answerC_better
from itertools import product
n=int(input())
ans=0
for i in range(3,10):
l=list(product(["3","5","7"],repeat=i))
for j in l:
if len(set(j))==3:
if int("".join(list(j)))<=n:
ans+=1
print(ans)
Since there are several prime number related libraries prepared in C ++ and it often takes time to handle prime numbers in Python, I implemented it in C ++ (I realized later that it is not so difficult to do it in Python after all). It was.). Also, since I started implementing it before thinking about it, there was a lot of waste such as trying to make a table of prime numbers.
Below, we will consider the correct answer. First, we noticed that, as a famous fact, ** integers of 1 or more that have an odd number of divisors are in the form of a square **. Also, in the sample case, 32400 was written as 75, so if you take the route of 32400, you can see that it is $ 180 $, which is $ 32400 = 2 ^ 4 \ times 3 ^ 4 \ times 5 ^ 2 $. I also found that there was. Here I recall a famous fact that is very important in this matter. ** When a number is factored as $ \ prod_ {i = 1} ^ {n} p_i ^ {q_i} $ ($ p_i $ is a different prime number, $ q_i $ is an integer greater than or equal to 1), that number The total number of divisors of is $ \ prod_ {i = 1} ^ {n} (q_i + 1) $ **. Therefore, since the total number of divisors is 75, consider $ p_i $ (i = 1 ~ n) such that ** $ \ prod_ {i = 1} ^ {n} (q_i + 1) = 75 $. It's good **. If you look for $ q_i $ before looking for such $ p_i $, there may be four sets of (4,4,2), (14,4), (24,2), (74) ( At first, I was only thinking about (4,4,2) and was impatient.)
↓ The following seems complicated, but if you can consider it so far, it is not so difficult. Therefore, when N is given, 1 to N are factored into prime numbers and the number of each prime number contained in N! Is counted [1], the prime number contained in 2 or more, the prime number contained in 4 or more, 14 By counting and recording the prime numbers that include more than 24, the prime numbers that contain 24 or more, and the prime numbers that contain 74 or more, [2], (4,4,2), (14,4), (24) It can be obtained as an answer by calculating how many cases there are in each case of, 2) and (74) [3] and outputting the total.
✳︎ Prime_factorize is a function that factorizes into prime factors and puts it in a vector, and the amount of calculation is $ O (\ sqrt {n}) $ (I'm sorry if I make a mistake. I think I will publish an article in Qiita as a library later.)
answerD.cc
//Include
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second
void Prime_factorize(vector<ll>& v,ll n){
if(n<=1) return;
ll l=ll(sqrt(n));
FOR(i,2,l){
if(n%i==0){
Prime_factorize(v,i);Prime_factorize(v,ll(n/i));return;
}
}
v.PB(n);return;
}
signed main(){
ll n;cin >> n;
map<ll,ll> m;
//[1]
FOR(i,1,n){
vector<ll> v;Prime_factorize(v,i);
REP(j,v.size()){
if(m.find(v[j])==m.end()){
m.insert(MP(v[j],1));
}else{
m[v[j]]++;
}
}
}
//[2]
vector<ll> ans(5,0);
for(auto i=m.begin();i!=m.end();++i){
if(i->S>=74)ans[0]++;
if(i->S>=24)ans[1]++;
if(i->S>=14)ans[2]++;
if(i->S>=4)ans[3]++;
if(i->S>=2)ans[4]++;
}
//[3]
ll rans=0;
rans+=ll((ans[4]-2)*ans[3]*(ans[3]-1)/2);
rans+=ans[0];
rans+=(ans[1]*(ans[4]-1));
rans+=(ans[2]*(ans[3]-1));
cout << rans << endl;
}
Recommended Posts