HackerRank Weekly Challenges - Week 3 3問目 - Prime Sum

Source

HackerRank Weekly Challenges - Week 3 3問目
problem statement（コンテストページ）
problem statement

問題概要

整数 $N$ はちょうど $K$ 個の素数の和として表すことができるかどうかを判定する問題．
同じ素数を何回使っても良い．

解法

ゴールドバッハの予想より，任意の $4$ 以上の偶数は $2$ つの素数の和で書ける．
（予想だがまだ判例が見つかっていないので，このぐらいのサイズなら正しいと仮定して良い）
場合分けしていく．
$K$ 個の素数の和は $2K$ 以上なので，$N < 2K$ なら不可能．
$K=1$ の場合は，$N$ が素数なら可能，そうでなければ不可能．
$N$ が偶数なら，ゴールドバッハの予想より可能．（$K-2$ 個だけ $2$ を使うことにすれば，ゴールドバッハの予想に帰着）
後は，$1$ 個素数を $2$ または $3$ を使うとして（$N \leftarrow N-2$，または，$N \leftarrow N-3$，$K \leftarrow K-1$），上の判定を $1$ 回だけ繰り返せば良い．
なぜなら，$K \geq 3$ ならできるだけ小さい素数を使用して $N$ を偶数にしてゴールドバッハの予想に帰着したいので $3$ を使うべきで，
$K = 2$ であれば，今，$N$ は奇数なので，素数として $2$ を $1$ 個は使わなければいけないから．
素数判定は，テストケースの数が大きいので，高速に行うために，例えば，ミラーラビン法などを用いれば良い．

C++によるスパゲッティなソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

/* 64桁2進数でのleading zeroの桁数 */
int ullNumberOfLeadingZerosTable[256]={8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int ullNumberOfLeadingZeros(ull x){
  int res=56; unsigned xl=x, xh=x>>32;
  if(xh)             res -= 32, xl = xh;
  if(xl&0xffff0000U) res -= 16, xl >>= 16;
  if(xl&0x0000ff00U) res -= 8,  xl >>= 8;
  return res + ullNumberOfLeadingZerosTable[xl];
}

/* (x*y)%m を求める (制約 x,y < m) */
ull ullMultipleMod(ull x, ull y, ull m){
  int k,loop=2;
  ull xlo,xhi,ylo,yhi,rlo,rhi,d1,d2,a,q,r,mask=0xffffffffULL;
  
  if(m<=mask) return (x*y)%m;
  
  xlo=(x&mask); xhi=(x>>32);
  ylo=(y&mask); yhi=(y>>32);
  rhi=xhi*yhi; rlo=xlo*ylo;
  a=(rlo>>32)+xhi*ylo;
  rhi+=(a>>32); a&=mask; a+=xlo*yhi; rhi+=(a>>32);
  rlo = (rlo&mask) | ((a&mask)<<32);
  
  k = ullNumberOfLeadingZeros(m);
  rhi = (rhi<<k)|(rlo>>(64-k));
  rlo<<=k; m<<=k;
  
  d1=(m>>32); d2=(m&mask);
  while(loop--){
    r = rhi/d1*d2;
    rhi = ( (rhi%d1 << 32) | (rlo>>32) );
    rlo = ( (rlo&mask) << 32 );
    if(rhi<r) rhi+=m-r; else rhi-=r;
    if(rhi>m) rhi+=m;
  }
  return rhi>>k;
}

/* (x^k)%m */
ull ullPowMod(ull x, ull k, ull m){
  ull res;
  if(k==0) return 1;
  res = ullPowMod(x,k/2,m);
  res = ullMultipleMod(res,res,m);
  if(k%2) res = ullMultipleMod(res,x,m);
  return res;
}

ull unsignedMillerRabinSuspectPow(int a, unsigned k, unsigned n){
  ull p=1; unsigned bit;
  for (bit=0x80000000U;bit;bit>>=1) {
    if(p>1)   p=(p*p)%n;
    if(k&bit) p=(p*a)%n;
  }
  return p;
}

int unsignedMillerRabinSuspect(int b, unsigned n){
  unsigned i,t=0,u=n-1; ull now, next;

  while(!(u&1)) t++, u>>=1;
  now = unsignedMillerRabinSuspectPow(b, u, n);

  for(i=1;i<=t;i++){
    next=(now*now)%n;
    if(next==1 && now!=1 && now!=n-1) return 0;
    now=next;
  }
  return next==1;
}

int unsignedMillerRabin(unsigned n){
  if(n<=1)return 0; if(n<=3)return 1; if(!(n&1))return 0;
  if(!unsignedMillerRabinSuspect(2,n)) return 0;
  if(n<=1000000){
    if(!unsignedMillerRabinSuspect(3,n)) return 0;
  } else {
    if(!unsignedMillerRabinSuspect(7,n)) return 0;
    if(!unsignedMillerRabinSuspect(61,n)) return 0;
  }
  return 1;
}

ull ullMillerRabinSuspectPow(ull a, ull k, ull n){
  ull p=1, bit;
  for (bit=0x8000000000000000ULL;bit;bit>>=1) {
    if(p>1)   p=ullMultipleMod(p,p,n);
    if(k&bit) p=ullMultipleMod(p,a,n);
  }
  return p;
}

int ullMillerRabinSuspect(ull b, ull n){
  ull i, t=0, u=n-1, now, next;

  while(!(u&1)) t++, u>>=1;
  now = ullMillerRabinSuspectPow(b, u, n);

  for(i=1;i<=t;i++){
    next=ullMultipleMod(now,now,n);
    if(next==1 && now!=1 && now!=n-1) return 0;
    now=next;
  }
  return now==1;
}

int ullMillerRabin(ull n){
  int i,lim;

  if(n<(1ULL<<32)) return unsignedMillerRabin(n);
  if(!(n&1)) return 0;
  
  if(n < 341550071728321ULL) lim=17; else lim=29;
  if(!ullMillerRabinSuspect(2,n)) return 0;
  for(i=3;i<=lim;i+=2) if(!ullMillerRabinSuspect(i,n)) return 0;

  return 1;
}


int solve(ll N, ll K, int r=0){
  if(N==0 && K==0) return 1;
  if(K==0) return 0;
  if(K==1){
    if(ullMillerRabin(N)) return 1;
    return 0;
  }
  if(N < 2*K) return 0;
  if(N%2==0 && N>=2*K) return 1;

  if(r==0){
    if(solve(N-2, K-1, 1)) return 1;
    if(solve(N-3, K-1, 1)) return 1;
  }
  return 0;
}

int main(){
  int i, j;
  int T;
  ll N, K;

  reader(&T);
  while(T--){
    reader(&N); reader(&K);
    if(solve(N,K)) writer("Yes\n"); else writer("No\n");
  }

  return 0;
}

Current time: 2024年04月26日02時52分48秒
Last modified: 2014年12月05日03時12分57秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w3
トップページに戻る

Logged in as: unknown user (not login)

ログイン：