プロジェクトオイラー 248 Numbers for which Euler’s totient function equals 13!

Numbers for which Euler’s totient function equals 13!

Problem 248

The first number n for which φ(n)=13! is 6227180929.
Find the 150,000^th such number.

http://projecteuler.net/problem=248


オイラーのファイ関数を通した結果が13！になるｎを小さいほうから見たとき15万番目となるｎを答えよ。



解法
ちょっとダメな感じです。
一分ルールを守れてるコードは書けたのですが。
無駄組み合わせもいくらか計算していてそれをファイ関数で力づくではじいています。
無駄組み合わせが一つも出ないのが理想なのですが？


コードの発想
オイラーのphi関数を通して13！と同じ素因数を持つものを生成します。
13！＝13*11*7*5＾２*3＾5*2＾10であることに注目します。

Ａ
ｎが13より大きな素因数ｐを持つ場合、その素因数ｐがｐ＾２などの二つ以上ｎに含まれる場合
phi関数を通しても13より大きな素因数を持つ数が生成されて不適。
よって13より大きな素因数ｐは一つでなくてはいけない。
またｐ＞13の素数の時ｐ-1が13より大きな素因数をもつならそれは13！の素因数でないものがphi関数を通して残ることになるのでｐ-1の素因数は13！の素因数、２，３、5,7,11,13でなくてはいけない。

Ｂ
ｎの13以下の素因数ｐはそのままｐが残っても問題ありません。
ｐ＾１でなくｐ＾２以上ならｐがphi関数を通してもその素因数が生き残ります。
ｎの素数ｐが13以下の素数なら、ｐ-1の２，３、5,7,11の素因数を考慮しておきます。

ＡとＢを合成して作ったphi関数の結果が
13！＝13*11*7*5＾２*3＾5*2＾10
となればそれは条件を満たします。


後はＡとＢの組み合わせを無駄なく全探索するだけです。

この発想で大丈夫なはずなのですが私のコードは何かミスがあるらしく。
無駄なパターンをいくつか余分に検討しています。
無駄なｎを生成した場合はph(n)iの結果が13!にならないならはじいています。
一応正答はしてるのですが何か微妙に間違ってるようです。


#include<stdio.h>
#include<set>
#include<iostream>

int counts[]={1,1,1,2,5,10};
int dells[6][6]={      {0,0,0,0,1,2},
                  {0,0,0,1,0,1},
                  {0,0,0,0,1,1},
                  {0,0,0,0,0,2},
                  {0,0,0,0,0,1},
                  {0,0,0,0,0,0}};
__int64 base[]={13,11,7,5,3,2};

std::set<__int64> all;

void saiki1(int,__int64);
void saiki2(int,int,__int64,__int64);


__int64 phi( __int64 n )
{
  __int64 res, p;

  res = n;
  if ( n % 2 == 0 ) {
    res /= 2;
    do { n /= 2; } while( n % 2 == 0 );
  }
  p = 3;
  while ( p <= n / p ) {
    if ( n % p == 0 ) {
      res = res / p * ( p - 1 );
      do { n /= p; } while( n % p == 0 );
    }
    p += 2;
  }
  if ( n > 1 ) { res = res / n * (n - 1); }

  return res;
}

bool isPrime(__int64 num){
      if(num<2)return false;
      for(__int64 i=2;i*i<=num;i+=1+(i%2)){
            if(num%i==0)return false;
      }
      return true;
}

void saiki2(int p1,int p2,__int64 m1,__int64 m2,__int64 loopCount){
      if(p2==6){
            if(m2>1&&isPrime(m2+1)==false)return ;
            if(loopCount!=0&&m2>13){
                  m2=m2;
            }else if(loopCount==0){
                  m2=0;
            }else{
                  return ;
            }
            bool ok=true;
            for(int i=0;i<6;i++){
                  if(counts[i]<dells[p1][i])ok=false;
            }
            if(ok==true){
                  for(int i=0;i<6;i++){
                        counts[i]-=dells[p1][i];
                  }
                  __int64 m3=1;
                  for(int i=0;i<=counts[p1];i++)m3*=base[p1];
                  saiki1(p1+1,m1*(m2+1)*m3);
                  for(int i=0;i<6;i++){
                        counts[i]+=dells[p1][i];
                  }
            }
            if(counts[p1]==0){
                  saiki1(p1+1,m1*(m2+1));
            }
            if(m2>13){
                  saiki2(p1,p1,m1*(m2+1),1,loopCount);
            }
      }else{
   
            __int64 m3=1;
            int temp=counts[p2];
            int start=0;
            if(p1==p2){
                  if(counts[p1]<loopCount)return ;
                  start=1;
                  if(start<loopCount)start=loopCount;
                  for(int i=0;i<start;i++){
                        m3*=base[p1];
                        counts[p1]--;
                  }
            }
         
            while(counts[p2]>=0){
                  if(p1==p2&&loopCount<start)loopCount=start;
                  int temp2=counts[p2];
                  saiki2(p1,p2+1,m1,m2*m3,loopCount);
                  counts[p2]=temp2-1;
                  m3*=base[p2];
                  start++;
            }
            counts[p2]=temp;
      }
}
void saiki1(int p1,__int64 m1){
      if(p1==6){
            if(phi(m1)==6227020800){
                  all.insert(m1);
            }else{
                  //std::cout<<"bad"<<m1<<" "<<phi(m1)<<"\n";
            }
      }else{
            saiki2(p1,p1,m1,1,1);
            saiki2(p1,6,m1,1,0);
      }

}

int main(){
      saiki1(0,1);
   
      std::set<__int64>::iterator it;
      std::cout<<all.size()<<"\n";
      int c=1;
      for(it=all.begin();it!=all.end();it++){
            if(c==150000){
                  std::cout<<"ans="<<(*it);
                  break;
            }
            c++;
      }
}