結果

問題 No.8038 フィボナッチ数列の周期
ユーザー mtsdmtsd
提出日時 2018-04-02 13:28:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 90 ms / 3,000 ms
コード長 3,256 bytes
コンパイル時間 1,037 ms
コンパイル使用メモリ 94,212 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-26 06:34:51
合計ジャッジ時間 2,726 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 3 ms
6,944 KB
testcase_09 AC 3 ms
6,944 KB
testcase_10 AC 3 ms
6,944 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 3 ms
6,944 KB
testcase_13 AC 3 ms
6,944 KB
testcase_14 AC 3 ms
6,944 KB
testcase_15 AC 3 ms
6,944 KB
testcase_16 AC 88 ms
6,944 KB
testcase_17 AC 89 ms
6,944 KB
testcase_18 AC 89 ms
6,940 KB
testcase_19 AC 86 ms
6,944 KB
testcase_20 AC 85 ms
6,940 KB
testcase_21 AC 90 ms
6,940 KB
testcase_22 AC 87 ms
6,940 KB
testcase_23 AC 88 ms
6,940 KB
testcase_24 AC 85 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘ll get_period(ll)’:
main.cpp:116:1: warning: control reaches end of non-void function [-Wreturn-type]
  116 | }
      | ^

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

long long  mod = 1000000007;
long long calc(long long  k,long long m){
	if(m==0)return 1;
	if(m==1)return k%mod;
	long long s = calc(k,m/2);
	if(m%2==0){
		return (s*s)%mod;
	}else{
		long long ans;
		ans = (s*s)%mod;
		return (k*ans)%mod;
	}
}
vector<ll> prime;
#define N 100000
bool arr[N];
void Eratosthenes(){
	for(int i = 0; i < N; i++){
		arr[i] = 1;
	}
	for(int i = 2; i < N; i++){
		if(arr[i]){
            prime.push_back((ll)i);
			for(int j = 0; i * (j + 2) < N; j++){
				arr[i *(j + 2)] = 0;
			}
		}
	}

}

vector<vector<ll> > mult(vector<vector<ll> >&u,vector<vector<ll> >&v,ll p){
    vector<vector<ll> >z(2,vector<ll>(2));
    z[0][0] = (u[0][0]*v[0][0]+u[0][1]*v[1][0])%p;
    z[0][1] = (u[0][0]*v[0][1]+u[0][1]*v[1][1])%p;
    z[1][0] = (u[1][0]*v[0][0]+u[1][1]*v[1][0])%p;
    z[1][1] = (u[1][0]*v[0][1]+u[1][1]*v[1][1])%p;
    return z;
}

vector<vector<ll> > mul(ll x,ll p){
    vector<vector<ll> > A(2,vector<ll>(2));
    A[0][0]=0;
    A[0][1]=1;
    A[1][0]=1;
    A[1][1]=1;
    if(x==1){ 
        return A;
    }
    if(x%2==0){
        vector<vector<ll> > z;
        z = mul(x/2,p);
        return mult(z,z,p);
    }else{
        vector<vector<ll> > z;
        z = mul(x/2,p);
        z = mult(z,z,p);
        return mult(z,A,p);
    }
}

ll get_period(ll p){
    if(p==2)return 3;
    if(p==5)return 20;
    set<ll> d;
    if(p%10==1||p%10==9){
        ll x = p-1;
        for(ll i=1;i<=sqrt(x)+1;i++){
            if(x%i==0){
                if(i%2==0)d.insert(i);
                if((x/i)%2==0)d.insert(x/i);
            }
        }   
    }else{
        ll x = 2*p+2;
        d.insert(x);
        for(ll i=1;i<=sqrt(x);i++){
            if(x%i==0){
                if((p+1)%i!=0)d.insert(i);
                if((p+1)%(x/i)!=0)d.insert(x/i);
            }
        } 
    }
    for(auto x:d){
        vector<vector<ll> > A(2,vector<ll>(2));
        A = mul(x,p);
        if(A[0][0]==1&&A[0][1]==0&&A[1][0]==0&&A[1][1]==1){
            return x;
        }
    }
}



int main(){
    int n;
    cin >> n;
    Eratosthenes();
    map<ll,ll> ans;
    for(int i=0;i<n;i++){
        ll p,k;
        cin >> p >> k;
        ll z = get_period(p);
        map<ll,ll>tmp;
        tmp[p]+=k-1;
        for(int i=0;i<prime.size();i++){
            if(prime[i]*prime[i]>z)break;
            while(1){
                if(z%prime[i]!=0)break;
                z/=prime[i];
                tmp[prime[i]]++;
            }
        }
        if(z!=1){
            tmp[z]++;
        }
        for(auto x:tmp){
            ans[x.first] = max(ans[x.first],x.second);
        }
    }
    ll s=1;
    for(auto x:ans){
        ll t = calc(x.first,x.second);
        s = (s*t)%mod;
    }
    cout << s << endl;
    return 0;
}
0