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

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

オイラープロジェクト121~130 - (2012/09/05 (水) 16:19:09) の編集履歴(バックアップ)


問い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 を求めよ.

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



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