「オイラープロジェクト121~130」の編集履歴(バックアップ)一覧に戻る
オイラープロジェクト121~130」を以下のとおり復元します。
*問い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 を求めよ.

モード演算は分けて個別に計算しても全部合わせて計算しても答えが変わらないということを利用してステップ単位で解きます。


 #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<<"?";
 }

復元してよろしいですか?