読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

Week of Code #22 - Number of Sequences

問題

Programming Problems and Competitions :: HackerRank

問題概要

素数nの数列aについて、以下の条件を満たしていれば「数列aniceである」とする:

  •  0 \le a_k \le k-1
  • kmの約数となっているような全ての(k,m)の組に対して、 a_k \equiv a_m \, (mod \, k)が成立

いま、数列がa_1 , a_2, ..., a_nとして与えられる。しかし、何箇所かの値が-1で与えられる時がある。その-1の部分の数字はそれぞれ変更することができる。この時、その変更によってniceな数列を作る方法は何通りあるか、10^9 + 7で割った余りを答えよ。

イデア

固定されたnがある。そしてp \le nを満たすそれぞれの素数pに対して、 p^{\alpha} \le nを満たす最大の整数 \alphaを求めておく。すると、「あらゆるniceな数列aは、次のようなペアの集合S(a) = \{ (p, a_{ p^{\alpha } }) \} によって一意に決定される」のである。

これを見ただけでは実際よくわからない。ということで片方向ずつ順番に考えていってみることにすると、あるniceな数列aが存在する時に、ある集合Sに対応するというのはこの集合の定義から考えて明らかである。

逆を考えてみる。ある集合Sをある数列aに対応させることを考えてみる。さて、素数pと整数kに対して、「kp^{\beta}で割り切れる」という条件を満たす最大の整数\betaを考えることができ、数列aniceであるから、

 a_{p^{\beta}} \equiv a_k  \, (mod \, p^{\beta}) a_{p^{\beta}} \equiv a_{p^{\alpha}} \, (mod \, p^{\beta} ) より

 a_k \equiv a_{p^{\beta}} \equiv a_{p^{\alpha}} \, (mod \, p^{\beta} ) が成り立つ。

そして、このときには中国剰余定理(参考1参考2)を使うことによってa_kの値は一意に決まる。

この中国剰余定理の適用が問題を解くキーになる。i: 1 \to nと順番に見ていき、a_iを決定していくと言う方針で見ていくことにすると、i=pq素因数分解される時には既にa_pa_qが決定していることからこの中国剰余定理によりa_{pq}も決定する。ということで自由度が残るのは1つの素数のみを素因数としてもる素因数冪番目のみに限られる。あとは順番に決定していきながら数を数え上げる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int N=100000;
const ll mod=1e9+7;

//i's divisor
vector<int> divisor[N+1];
//if i is power of a prime, restore the prime
int prime_pow[N+1]={0};

int main()
{
    int n;
    cin >>n;
    vector<int> a(n+1);
    for(int i=1; i<=n; ++i) scanf(" %d", &a[i]);

    for(ll i=1; i<=n; ++i)
    {
        // add divisor
        for(ll j=i; j<=n; j+=i) divisor[j].pb(i);

        // if i is prime:
        if(divisor[i].size()==2)
        {
            // powers of i restore prime i
            for(ll j=i*i; j<=n; j*=i) prime_pow[j]=i;
        }

        if(a[i]!=-1)
        {
            // i is determined,so divisors of i should be determined
            for(int d:divisor[i])
            {
                if(d==i) continue;
                if(a[d]!=-1 && a[d]!=a[i]%d)
                {
                    // a is not 'nice'
                    printf("0\n");
                    return 0;
                }

                a[d]=a[i]%d;
            }
        }
    }

    ll ans=1;

    for(ll i=1; i<=n; ++i)
    {
        if(divisor[i].size()==2)
        {
            if(a[i]==-1) (ans*=i)%=mod;
        }
        else
        {
            if(prime_pow[i]!=0 && a[i]==-1) (ans*=prime_pow[i])%=mod;
        }
    }

    cout << ans << endl;
    return 0;
}