F - L to R Multiply

2 secs 1024 MB

この問題では約数列挙、再帰関数を問います。

問題の $a_i$ は $K$ の約数 (負整数を含む) であることは明らかです。問題の条件を満たすような $(a_1,a_2,...,a_n)$ は再帰関数を用いて実装できますが、負の約数を含めて調べてしまうとあるケース※ $_1$ では時間制限に間に合わなくなってしまいます。なのでここでは時間に間に合うように工夫しなければなりません。

実は、 $K$ の正の約数だけ調べてから、候補となる $a_i$ を再帰的に探索することが適切です※ $_2$ 。
$K=0$ 、または $K$ が素数の場合においては条件文で判定することに注意※ $_3$ してください。以下の解答例(C++,Python)も参考にしてみてください。

※ $_1$ 例えば $L=-10^6,R=10^6,K=720720$ などのケースが該当します。この理由は $K$ の正の約数の個数がより多いためです(このような数は高度合成数と呼ばれます。ここでは説明は省略します)

※ $_2$
次のそれぞれの場合について、以下のように考えることができます。

$L\le -1\le R$ のとき: $K$ の正負は考えなくても良い (最終的な答えで、辻褄があうように $-1$ を適宜かけ合わせればよいため)
$R\lt -1$ のとき: 制約から $L$ も負であるため、 $K$ の正の約数にすべて $-1$ を掛け合わせればよい (確かに $L\le -1\le R$ とはならないが、候補となる約数はすべて負となるため)
$L\gt -1$ のとき: 制約から $R$ も正であるため、最終的な答えには何も影響しない

したがって $K$ の正の約数を候補に入れながら $A$ を探索することで、負の約数を考慮せずに実装できます。

また $K\gt 0$ なら負の約数を偶数個含んでいる( $0$ 個でもよい)のと、 $K\lt 0$ なら奇数個含んでいることが必要であることに注意してください。

※ $_3$
実装方法によっては、 $1$ や $0$ を候補にすると関数内で無限ループを起こす可能性があります。なのでその時に限り、以下の条件のいずれか一つをみたすことができるか判定すればよいです。

$L\le K\le R$ であるか？
$L\le -K\le R$ かつ $L\le -1\le R$ であるか？

xxxxxxxxxx
 
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(all(A))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<P,vector<P>,greater<P>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<int>>;
using SGraph = vector<set<ll>>;
template <typename T>
int siz(T& a){return (int)a.size();}
​
void fdiv(vector<int> &D,int n){
    for(int i = 2; i*i <= n; i++){
        if(n%i == 0){
            ll d = n/i;
            D.push_back(d);
            if(d != i){
                D.push_back(i);
            }
        }
    }
    sort(all(D));
}
​
int l,r,k;
bool ok = 0;
bool inrange(int x){ return (l <= x && x <= r); }
​
void dfs(const vector<int> &D,vector<int> &div,int now,int pos){
    if(now == 1){
        bool aok = 1;
        int mcnt = 0;
        for(auto d : div){
            if(!inrange(d)){
                if(inrange(-d)) mcnt++;
                else aok = 0;
            }
        }
        if(aok){
            if(((k > 0 && mcnt%2 == 1) || (k < 0 && mcnt%2 == 0)) && inrange(-1)) k *= -1;
            if((k > 0 && mcnt%2 == 0) || (k < 0 && mcnt%2 == 1)) ok = 1;
        }
        return;
    }
​
    srep(i,pos,siz(D)){
        if(now%D[i] != 0) continue;
        div.push_back(D[i]);
        dfs(D,div,now/D[i],i);
        div.pop_back();
    }
}
​
bool primecheck(ll x){ return (inrange(x) || (inrange(-x) && inrange(-1))); }
​
int main(void){
    cin >> l >> r >> k;
    vector<int> div,D;
    if(k != 0){
        fdiv(D,abs(k));
        dfs(D,div,abs(k),0);
    }
​
    cout << (ok || primecheck(k) ? "Yes" : "No");
}
​

xxxxxxxxxx
 
def fdiv(D,x):
    for i in range(2,x):
        if i*i > x:
            break
        if x%i != 0:
            continue
        d = x//i
        D.append(d)
        if d != i:
            D.append(i)
    D.sort()
    return
​
def inrange(x):
    return (l <= x <= r)
​
def dfs(D,div,now,pos):
    if now == 1:
        aok = 1
        mcnt = 0
        for d in div:
            if not inrange(-d):
                if not inrange(d):
                    aok = 0
            else:
                mcnt += 1
        if aok == 1:
            global k
            if inrange(-1) and ((k > 0 and mcnt%2 == 1) or (k < 0 and mcnt%2 == 0)):
                k *= -1
            if (k > 0 and mcnt%2 == 0) or (k < 0 and mcnt%2 == 1):
                #print(*div)
                global ok
                ok = 1
        return
    for i in range(pos,len(D)):
        if now%D[i] != 0:
            continue
        div.append(D[i])
        dfs(D,div,now//D[i],i)
        div.pop()
​
def primecheck(x):
    return (inrange(x) or (inrange(-x) and inrange(-1)))
​
l,r,k = map(int,input().split())
div = []
D = []
​
ok = 0
if k != 0:
    fdiv(D,abs(k))
    dfs(D,div,abs(k),0)
​
print("Yes" if ok or primecheck(k) else "No")
​