QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #77192 | #1482. Pisano Periods | eee | AC ✓ | 6ms | 3492kb | C++14 | 2.6kb | 2023-02-13 09:53:18 | 2023-02-13 09:53:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mll map<ll,ll>
#define vll vector<ll>
vll sieve(ll n){
vll primes;
vector<bool> is_prime(n,true);
for(int i = 2;i <n;++i){
if(is_prime[i]){
primes.push_back(i);
for(ll j = i * i;j< n; j+=i){
is_prime[j] = false;
}
}
}
return primes;
}
mll prime_factors( ll val){
mll factors;
for(ll i = 2;i*i <= val;++i){
while(val% i == 0){
factors[i]++;
val/=i;
}
}
if(val > 1){
factors[val]++;
}
return factors;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
// ll c = t;
// vll primes;
// vector<bool> is_prime(1000000,true);
// for(ll i = 2;i <=1000000;++i){
// if(is_prime[i]){
// primes.push_back(i);
// for(ll j = i * i;j< 1000000; j+=i){
// is_prime[j] = false;
// }
// }
// }
// vll to_chk;
// for(ll& v: primes){
// ll tmp = v;
// to_chk.push_back(tmp);
// while(tmp*v <= 1000000){
// tmp*=v;
// to_chk.push_back(tmp);
// }
// }
// cout << to_chk.size() << endl;
// unordered_map<ll,ll> cycle_size;
// for(ll& n:to_chk){
// ll a = 1;
// ll b = 1;
// ll ct = 0;
// while(!(b == 0 && a == 1)){
// ll tmp = a+b;
// a = b;
// b = tmp%n;
// ct++;
// }
// cycle_size[n] = ct+2;
// // cout << "{" << n << "," << ct+2 << "},";
// }
while(t--){
ll cs,n;
cin >> cs >> n;
// vector<ll> cyc;
// for(ll i = 2;i*i <= n;++i){
// ll toa = 1;
// while(n% i == 0){
// toa *= i;
// n/=i;
// }
// if(toa > 1){
// cyc.push_back(cycle_size[toa]);
// }
// }
// if(n > 1){
// cyc.push_back(cycle_size[n]);
// }
// ll ans = 1;
// for(ll& i:cyc){
// ans*=i;
// }
ll a = 1;
ll b = 1;
ll ct = 0;
while(!(b == 0 && a == 1)){
ll tmp = a+b;
a = b;
b = tmp%n;
ct++;
}
// cycle_size[n] = ct+2;
// cout << "{" << n << "," << ct+2 << "},";
cout << cs << " " << ct+2 << endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 3492kb
input:
1000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
1 3 2 8 3 6 4 20 5 24 6 16 7 12 8 24 9 60 10 10 11 24 12 28 13 48 14 40 15 24 16 36 17 24 18 18 19 60 20 16 21 30 22 48 23 24 24 100 25 84 26 72 27 48 28 14 29 120 30 30 31 48 32 40 33 36 34 80 35 24 36 76 37 18 38 56 39 60 40 40 41 48 42 88 43 30 44 120 45 48 46 32 47 24 48 112 49 300 50 72 51 84 5...
result:
ok 1000 lines