結果

問題 No.8038 フィボナッチ数列の周期
ユーザー mtsd
提出日時 2018-04-02 13:28:17
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0