QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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;
}
Details
Tip: Click on the bar to expand more detailed information
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