Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2278-e6504f44
この記事にトラックバックする(FC2ブログユーザー)

SRM552 DIV1 HARD - HolyNumbers (この記事を編集する[管理者用])

Source

TopCoder SRM552 DIV1 HARD (900pt)
Problem Statement

問題概要

N以下の正整数で,以下の条件をみたすものがいくつあるかを求める問題.
 Nを素因数分解した時,出てくる素因数は全てM以下.
 素因数pを持つならば,素因数分解した時に,素数pは偶数回出てくる.(詳細は問題文参照)
Nは10^10以下,Mは10^6以下.

解法

基本的には枝刈り全探索すれば良い.
小さい素数から順番に,それが何回素因数分解した時に登場するかを決定していく.
ただし,(N / 現在の数) が (現在の素数の2乗) を上回ったら,後は2個以上の素数をかけることができないから,
何も書けない,1個素数をかける,しか選択肢がなく,かけることができる素数の数は簡単に求めれるから端折る.
計算量は謎いけど,最悪ケースで0.4秒以下ぐらいで終わった.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

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

#define ll long long

int getPrime(int n,int p[]){int i,j,n2=n/2;rep(i,n2)p[i]=1;for(i=3;i*i<n;i+=2)if(p[i>>1])for(j=(i*i)>>1;j<n2;j+=i)p[j]=0;j=1;p[0]=2;REP(i,1,n2)if(p[i])p[j++]=i*2+1;return j;}
int p[1100000], ps; ll p2[1100000], p3[1100000];
int bef[1100000];

ll res, n;

void solve(int depth, ll now){
  ll k;

  if(depth == ps){ res++; return; }

  if(now * p2[depth] > n || now * (double)p2[depth] > n + 100000){
    k = n / now;
    if(k > 1000010) k = 1000010;
    if(bef[k] >= depth) res += bef[k] - depth + 1;
    res++;
    return;
  }

  solve(depth+1, now);
  
  now *= p[depth];
  for(;;){
    solve(depth+1, now);
    if(now * p2[depth] > n || now * (double)p2[depth] > n + 100000) break;
    now *= p2[depth];
  }
}

class HolyNumbers {
public:
ll count(ll upTo, int maximalPrime) {
  int i,j,k;

  ps = getPrime(maximalPrime + 10, p);
  while(ps > 0 && p[ps-1] > maximalPrime) ps--;

  rep(i,ps) p2[i] = p[i] * (ll)p[i];
  rep(i,ps) p3[i] = p2[i] * p[i];

  rep(i,1001000) bef[i] = -1;
  rep(i,ps) bef[p[i]] = i;
  REP(i,1,1001000) if(bef[i]==-1) bef[i] = bef[i-1];

  n = upTo;
  res = 0;

  solve(0, 1);

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2278-e6504f44
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。