Week of Code #22 - Number of Sequences

問題

Programming Problems and Competitions :: HackerRank

問題概要

要素数の数列について、以下の条件を満たしていれば「数列はniceである」とする：

• 
• がの約数となっているような全てのの組に対して、が成立

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

アイデア

固定されたがある。そしてを満たすそれぞれの素数に対して、を満たす最大の整数を求めておく。すると、「あらゆるniceな数列は、次のようなペアの集合によって一意に決定される」のである。

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

逆を考えてみる。ある集合をある数列に対応させることを考えてみる。さて、素数と整数に対して、「がで割り切れる」という条件を満たす最大の整数を考えることができ、数列はniceであるから、

と より

が成り立つ。

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

この中国剰余定理の適用が問題を解くキーになる。と順番に見ていき、を決定していくと言う方針で見ていくことにすると、と素因数分解される時には既にとが決定していることからこの中国剰余定理によりも決定する。ということで自由度が残るのは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;
}