※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「オイラープロジェクト121~130」の編集履歴(バックアップ)一覧に戻る

オイラープロジェクト121~130 - (2012/09/05 (水) 17:02:23) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

 *問い123
 pn を n 番目の素数とする. (p1 = 2, p2 = 3, ...) r を (pn - 1)n + (pn + 1)n を pn2 で割った余りとする.
 例えば, n = 3 のとき, p3 = 5 であり, 43 + 63 = 280 ≡ 5 mod 25.
 余り r が 109 より大きくなる n の最小値は 7037 である.
 余り r が 1010 より大きくなる最初の n を求めよ.
 
 モード演算は分けて個別に計算しても全部合わせて計算しても答えが変わらないということを利用してステップ単位で解きます。
 
 高速化しようと考え
-n^23=n^16*n^4*n^2*n^1のように累乗が分解出来る性質を利用して解こうとしたらint64で溢れるので上手くいきません。
+n^23=n^16*n^4*n^2*n^1のように累乗が2^累乗の指数に分解出来る性質を利用して解こうとしたらint64で溢れるので上手くいきません。
 Lispなら高速化は簡単ですがC++では多倍張整数を用意しないと無理かもしれません。
 
 
 
 
  #include<stdio.h>
  #include<vector>
  #include<iostream>
  const int up=1000000;
  std::vector<__int64> sosuu; 
  bool so[up];
  void setSo(){
 	int i2;
 	memset(so,true,sizeof(so));
 	sosuu.push_back(2);
 	for(int i=3;i<=up;i+=2){
 		if(so[i]==false)continue;
 		sosuu.push_back(i);
 		i2=i*2;
 		for(int j=i*3;j<up;j+=i2){
 			so[j]=false;
 		}
 	}
  }
  int main(){
 	setSo();
 	__int64 p,pd,pu,p2,calcD,calcU,ten=1;
 	for(int i=0;i<10;i++){
 		ten*=10;
 	}
 	for(int i=0;i<sosuu.size();i++){
 		p=sosuu[i];
 		p2=p*p;
 		calcD=pd=p-1;
 		calcU=pu=p+1;
 		for(int n=0;n<i;n++){
 			calcD=(calcD*pd)%p2;
 			calcU=(calcU*pu)%p2;
 		}
 		//std::cout<<(calcD+calcU)%p2<<"\n";
 		if((calcU+calcD)%p2>ten){
 			std::cout<<i+1;
 			break;
 		}
 	}
 	std::cout<<"?";
  }