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

裏紙

ほぼ競プロ、たまに日記

GCJ 2016 Qual Round C - Coin Jam

問題

Dashboard - Qualification Round 2016 - Google Code Jam

問題概要

jamcoinという長さN(\ge 2) の文字列がある.jamcoinは以下の性質を満たす:

  • 全ての桁が0か1で構成される.
  • 最上位の桁と最下位の桁は必ず1である.
  • この文字列を2進数から10進数のどの数として解釈したとしても,その数は全て素数ではない.

長さNが与えられるので,jamcoinとしてあり得るものをJ個答えよ(J個存在することは保証されている).また,それぞれの数に対してjamcoinを2進数から10進数で解釈した時に「非自明な」約数(1と自分自身以外.つまり素数でないことを示せる数)をそれぞれ1つずつ答えよ.

イデア

smallは愚直にループしてjamcoinがJ個見つかるまで調べ続けた.largeもNJが分かっていたので,埋め込むという手も無くはなかったけど,まあ予選だしもっといい方法があるだろうということで...

largeでは10進数で32桁の数字が与えられるということなので,long longにも収めることが出来ない,xの約数を探すために,2から\sqrt{x}の数で順番に割り切れるか試していくのでは間に合わない,と様々なところで問題が発生する.

(案1)

これに関しては全てに対して試すのではなく,ある程度の境界を用意(1000までとか)して,そこまでで割り切れなかったらその数字は諦めてしまおうというものである.与えられるJNに対して余裕があるから多分これでも足りるだろう,と考える(実際に実行してみて足りていればそれで十分じゃないか).それで,間のN-2桁を乱択で試しても十分に間に合う.

(案2)

実はそのようなことを悩まなくても,確実に2進数から10進数のいずれで解釈しても「非自明な」約数があるようなjamcoin文字列を生成することができてしまう.今回は与えられるNがsmallもlargeもともに偶数であることに注目すると,N=2kとし,jamcoinの文字列を x_{2k} x_{2k-1} ... x_{k+1} x_k x_{k-1} ... x_2 x_1 x_0と表すことにすると,真ん中でちょうど分けて長さkの文字列を得た時に2つが同じならそれは必ず因数分解出来るので,非自明な約数を持つようにすることができる.

なぜなら,上半分の文字列が下半分の文字列に一致する時,文字列の形はx_k x_{k-1} ... x_2 x_1 x_0 x_k x_{k-1} ... x_2 x_1 x_0という形になる.そして,このjamcoinをb進数と見なすと,10進数で表すところの x_k b^{2k-1} + x_{k-1} b^{2k-2} + ... + x_2 b^{k+2} +x_1 b^{k+1} +x_0 b^{k} + x_k b^{k-1} + x_{k-1} b^{k-2} + ... + x_1 b + x_0という値になり,この数は因数分解できて (x_k b^{k-1} + x_{k-1} b^{k-2} + ... + x_1 b + x_0) (b^k +1) となるので,かならずb^k +1が約数になることが分かる.あとは条件をみたすように先頭と末尾を1にした文字列をJ個生成して,この約数を答えとすれば良い.

実装(C++)

bitcoinとしての文字列を乱択で試し,J個見つかるまでやり続ける方法

#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 mp make_pair
#define pb push_back
#define fi first
#define se second

//sをb進数として解釈した時にxで割り切れるか
bool div(string s, int b, int x)
{
    int now=0;
    rep(i,s.size())
    {
        now = now*b+(s[i]-'0');
        now%=x;
    }

    return (now==0);
}

int main()
{
    int T;
    cin >>T;
    rep(t,T)
    {
        int N,J;
        cin >>N >>J;

        printf("Case #%d:\n", t+1);

        int ct=0;
        set<string> found;
        while(ct<J)
        {
            //ランダムな文字列生成
            string s="1";
            rep(i,N-2)
            {
                if(rand()%2==1) s+="1";
                else s+="0";
            }
            s+="1";

            //すでにある
            if(found.find(s)!=found.end()) continue;

            bool valid=true;
            vector<int> ans;

            //i進数で解釈した時に
            for(int i=2; i<=10; ++i)
            {
                bool ok=false;
                //jで割り切れるか
                for(int j=2; j<=1000; ++j)
                {
                    if(div(s,i,j))
                    {
                        ok=true;
                        ans.pb(j);
                        break;
                    }
                }

                if(!ok)
                {
                    valid=false;
                    break;
                }
            }

            if(valid)
            {
                ++ct;
                found.insert(s);

                cout << s;
                for(const auto& x:ans) cout << " " << x;
                cout << endl;
            }
        }
    }
    return 0;
}

bitcoinを上半分と下半分に分け下半分の数を約数として答える方法

#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 mp make_pair
#define pb push_back
#define fi first
#define se second

int main()
{
    int T;
    cin >>T;
    rep(t,T)
    {
        int N,J;
        cin >>N >>J;

        printf("Case #%d:\n", t+1);

        N/=2;

        ll pw[11];
        rep(i,11) pw[i]=1;
        for(ll i=1; i<=10; ++i)
        {
            rep(j,N) pw[i]*=i;
            pw[i]+=1;
        }

        //順番に文字列をJ個生成
        rep(i,J)
        {
            string s="1";
            rep(j,N-2)
            {
                if(i>>j&1) s+="1";
                else s+="0";
            }
            s+="1";

            cout << s+s;
            for(int j=2; j<=10; ++j)
                cout << " " << pw[j];
            cout << endl;
        }
    }
    return 0;
}