結果
| 問題 | No.303 割れません |
| ユーザー |
 beet
|
| 提出日時 | 2018-11-23 17:17:15 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,985 bytes |
| コンパイル時間 | 2,409 ms |
| コンパイル使用メモリ | 220,352 KB |
| 実行使用メモリ | 28,504 KB |
| 最終ジャッジ日時 | 2023-08-26 04:32:18 |
| 合計ジャッジ時間 | 35,906 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,380 KB |
| testcase_01 | AC | 2 ms
4,376 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 2,229 ms
8,948 KB |
| testcase_04 | AC | 6,480 ms
14,436 KB |
| testcase_05 | AC | 6,497 ms
14,604 KB |
| testcase_06 | AC | 6,342 ms
14,496 KB |
| testcase_07 | TLE | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename K>
struct Matrix{
typedef vector<K> arr;
typedef vector<arr> mat;
mat dat;
Matrix(size_t r,size_t c):dat(r,arr(c,K())){}
Matrix(mat dat):dat(dat){}
size_t size() const{return dat.size();};
bool empty() const{return size()==0;};
arr& operator[](size_t k){return dat[k];};
const arr& operator[](size_t k) const {return dat[k];};
static Matrix cross(const Matrix &A,const Matrix &B){
Matrix res(A.size(),B[0].size());
for(int i=0;i<(int)A.size();i++)
for(int j=0;j<(int)B[0].size();j++)
for(int k=0;k<(int)B.size();k++)
res[i][j]+=A[i][k]*B[k][j];
return res;
}
static Matrix identity(size_t n){
Matrix res(n,n);
for(int i=0;i<(int)n;i++) res[i][i]=K(1);
return res;
}
Matrix pow(long long n) const{
Matrix a(dat),res=identity(size());
while(n){
if(n&1) res=cross(res,a);
a=cross(a,a);
n>>=1;
}
return res;
}
template<typename T> using ET = enable_if<is_floating_point<T>::value>;
template<typename T> using EF = enable_if<!is_floating_point<T>::value>;
template<typename T, typename ET<T>::type* = nullptr>
static bool is_zero(T x){return abs(x)<1e-8;}
template<typename T, typename EF<T>::type* = nullptr>
static bool is_zero(T x){return x==T(0);}
static Matrix gauss_jordan(const Matrix &A,const Matrix &B){
int n=A.size(),l=B[0].size();
Matrix C(n,n+l);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
C[i][j]=A[i][j];
for(int j=0;j<l;j++)
C[i][n+j]=B[i][j];
}
for(int i=0;i<n;i++){
int p=i;
for(int j=i;j<n;j++)
if(abs(C[p][i])<abs(C[j][i])) p=j;
swap(C[i],C[p]);
if(is_zero(C[i][i])) return Matrix(0,0);
for(int j=i+1;j<n+l;j++) C[i][j]/=C[i][i];
for(int j=0;j<n;j++){
if(i==j) continue;
for(int k=i+1;k<n+l;k++)
C[j][k]-=C[j][i]*C[i][k];
}
}
Matrix res(n,l);
for(int i=0;i<n;i++)
for(int j=0;j<l;j++)
res[i][j]=C[i][n+j];
return res;
}
Matrix inv() const{
Matrix B=identity(size());
return gauss_jordan(*this,B);
}
K determinant() const{
Matrix A(dat);
K res(1);
int n=size();
for(int i=0;i<n;i++){
int p=i;
for(int j=i;j<n;j++)
if(abs(A[p][i])<abs(A[j][i])) p=j;
if(i!=p) swap(A[i],A[p]),res=-res;
if(is_zero(A[i][i])) return K(0);
res*=A[i][i];
for(int j=i+1;j<n;j++) A[i][j]/=A[i][i];
for(int j=i+1;j<n;j++)
for(int k=i+1;k<n;k++)
A[j][k]-=A[j][i]*A[i][k];
}
return res;
}
static arr linear_equations(const Matrix &A,const arr &b){
Matrix B(b.size(),1);
for(int i=0;i<(int)b.size();i++) B[i][0]=b[i];
Matrix tmp=gauss_jordan(A,B);
arr res(tmp.size());
for(int i=0;i<(int)tmp.size();i++) res[i]=tmp[i][0];
return res;
}
static K sigma(K x,long long n){
Matrix A(2,2);
A[0][0]=x;A[0][1]=0;
A[1][0]=1;A[1][1]=1;
return A.pow(n)[1][0];
}
};
struct bigint {
using ll = long long;
constexpr static ll base = 1000000000;
constexpr static ll base_digits = 9;
vector<ll> a;
ll sign;
bigint():sign(1){}
bigint(ll v){
*this=v;
}
bigint(const string &s){
read(s);
}
void operator=(const bigint &v){
sign=v.sign;
a=v.a;
}
void operator=(ll v){
sign=1;
if(v<0) sign=-1,v=-v;
for(;v>0;v=v/base) a.push_back(v%base);
}
bigint operator+(const bigint &v) const{
if(sign==v.sign){
bigint res=v;
for(ll i=0,carry=0;i<(ll)max(a.size(),v.a.size())||carry;++i){
if(i==(ll)res.a.size()) res.a.push_back(0);
res.a[i]+=carry+(i<(ll)a.size()?a[i]:0);
carry=res.a[i]>=base;
if(carry) res.a[i]-=base;
}
return res;
}
return *this -(-v);
}
bigint operator-(const bigint &v) const{
if(sign==v.sign){
if(abs()>=v.abs()){
bigint res=*this;
for(ll i=0,carry=0;i<(ll)v.a.size()||carry;++i){
res.a[i]-=carry+(i<(ll)v.a.size()?v.a[i]:0);
carry=res.a[i]<0;
if(carry) res.a[i]+=base;
}
res.trim();
return res;
}
return -(v-*this);
}
return *this+(-v);
}
void operator*=(ll v){
if(v<0) sign=-sign,v=-v;
for(ll i=0,carry=0;i<(ll)a.size()|| carry;++i){
if(i ==(ll)a.size()) a.push_back(0);
ll cur=a[i] *(ll)v+carry;
carry=(ll)(cur/base);
a[i]=(ll)(cur%base);
// asm("divl %%ecx" : "=a"(carry),"=d"(a[i]) : "A"(cur),"c"(base));
}
trim();
}
bigint operator*(ll v) const{
bigint res=*this;
res *=v;
return res;
}
friend pair<bigint,bigint> divmod(const bigint &a1,const bigint &b1){
ll norm=base/(b1.a.back()+1);
bigint a=a1.abs()*norm;
bigint b=b1.abs()*norm;
bigint q,r;
q.a.resize(a.a.size());
for(ll i=a.a.size()-1;i>=0;i--){
r *=base;
r+=a.a[i];
ll s1=r.a.size()<=b.a.size() ? 0 : r.a[b.a.size()];
ll s2=r.a.size()<=b.a.size()-1 ? 0 : r.a[b.a.size()-1];
ll d=((ll)base*s1+s2)/b.a.back();
r-=b*d;
while(r<0) r+=b,--d;
q.a[i]=d;
}
q.sign=a1.sign*b1.sign;
r.sign=a1.sign;
q.trim();
r.trim();
return make_pair(q,r/norm);
}
bigint operator/(const bigint &v) const{
return divmod(*this,v).first;
}
bigint operator%(const bigint &v) const{
return divmod(*this,v).second;
}
void operator/=(ll v){
if(v<0) sign=-sign,v=-v;
for(ll i=(ll)a.size()-1,rem=0;i>=0;--i){
ll cur=a[i]+rem *(ll)base;
a[i]=(ll)(cur/v);
rem=(ll)(cur%v);
}
trim();
}
bigint operator/(ll v) const{
bigint res=*this;
res/=v;
return res;
}
ll operator%(ll v) const{
if(v<0) v=-v;
ll m=0;
for(ll i=a.size()-1;i>=0;--i) m=(a[i]+m *(ll)base)%v;
return m*sign;
}
void operator+=(const bigint &v){
*this=*this+v;
}
void operator-=(const bigint &v){
*this=*this-v;
}
void operator*=(const bigint &v){
*this=*this*v;
}
void operator/=(const bigint &v){
*this=*this/v;
}
bool operator<(const bigint &v) const{
if(sign!=v.sign) return sign<v.sign;
if(a.size()!=v.a.size()) return a.size()*sign<v.a.size()*v.sign;
for(ll i=a.size()-1;i>=0;i--)
if(a[i]!=v.a[i]) return a[i]*sign<v.a[i]*sign;
return false;
}
bool operator>(const bigint &v) const{
return v<*this;
}
bool operator<=(const bigint &v) const{
return !(v<*this);
}
bool operator>=(const bigint &v) const{
return !(*this<v);
}
bool operator==(const bigint &v) const{
return !(*this<v)&&!(v<*this);
}
bool operator!=(const bigint &v) const{
return *this<v|| v<*this;
}
void trim(){
while(!a.empty()&&!a.back()) a.pop_back();
if(a.empty()) sign=1;
}
bool isZero() const{
return a.empty()||(a.size()==1&&!a[0]);
}
bigint operator-() const{
bigint res=*this;
res.sign=-sign;
return res;
}
bigint abs() const{
bigint res=*this;
res.sign*=res.sign;
return res;
}
ll longValue() const{
ll res=0;
for(ll i=a.size()-1;i>=0;i--) res=res*base+a[i];
return res*sign;
}
friend bigint gcd(const bigint &a,const bigint &b){
return b.isZero() ? a : gcd(b,a%b);
}
friend bigint lcm(const bigint &a,const bigint &b){
return a/gcd(a,b)*b;
}
void read(const string &s){
sign=1;
a.clear();
ll pos=0;
while(pos<(ll)s.size()&&(s[pos]=='-'|| s[pos]=='+')){
if(s[pos]=='-') sign=-sign;
++pos;
}
for(ll i=s.size()-1;i>=pos;i-=base_digits){
ll x=0;
for(ll j=max(pos,i-base_digits+1);j<=i;j++) x=x*10+s[j]-'0';
a.push_back(x);
}
trim();
}
friend istream &operator>>(istream &stream,bigint &v){
string s;
stream>>s;
v.read(s);
return stream;
}
friend ostream &operator<<(ostream &stream,const bigint &v){
if(v.sign==-1) stream<<'-';
stream<<(v.a.empty() ? 0 : v.a.back());
for(ll i=(ll)v.a.size()-2;i>=0;--i)
stream<<setw(base_digits)<<setfill('0')<<v.a[i];
return stream;
}
static vector<ll> convert_base(const vector<ll> &a,
ll old_digits,ll new_digits){
vector<ll> p(max(old_digits,new_digits)+1);
p[0]=1;
for(ll i=1;i<(ll)p.size();i++) p[i]=p[i-1]*10;
vector<ll>res;
ll cur=0;
ll cur_digits=0;
for(ll i=0;i<(ll)a.size();i++){
cur+=a[i]*p[cur_digits];
cur_digits+=old_digits;
while(cur_digits>=new_digits){
res.push_back(signed(cur%p[new_digits]));
cur/=p[new_digits];
cur_digits-=new_digits;
}
}
res.push_back((signed)cur);
while(!res.empty()&&!res.back()) res.pop_back();
return res;
}
typedef vector<ll> vll;
static vll karatsubaMultiply(const vll &a,const vll &b){
ll n=a.size();
vll res(n+n);
if(n<=32){
for(ll i=0;i<n;i++)
for(ll j=0;j<n;j++)
res[i+j]+=a[i]*b[j];
return res;
}
ll k=n>>1;
vll a1(a.begin(),a.begin()+k);
vll a2(a.begin()+k,a.end());
vll b1(b.begin(),b.begin()+k);
vll b2(b.begin()+k,b.end());
vll a1b1=karatsubaMultiply(a1,b1);
vll a2b2=karatsubaMultiply(a2,b2);
for(ll i=0;i<k;i++) a2[i]+=a1[i];
for(ll i=0;i<k;i++) b2[i]+=b1[i];
vll r=karatsubaMultiply(a2,b2);
for(ll i=0;i<(ll)a1b1.size();i++) r[i]-=a1b1[i];
for(ll i=0;i<(ll)a2b2.size();i++) r[i]-=a2b2[i];
for(ll i=0;i<(ll)r.size();i++) res[i+k]+=r[i];
for(ll i=0;i<(ll)a1b1.size();i++) res[i]+=a1b1[i];
for(ll i=0;i<(ll)a2b2.size();i++) res[i+n]+=a2b2[i];
return res;
}
bigint operator*(const bigint &v) const{
vector<ll>a6=convert_base(this->a,base_digits,6);
vector<ll>b6=convert_base(v.a,base_digits,6);
vll a(a6.begin(),a6.end());
vll b(b6.begin(),b6.end());
while(a.size()<b.size()) a.push_back(0);
while(b.size()<a.size()) b.push_back(0);
while(a.size() &(a.size()-1)) a.push_back(0),b.push_back(0);
vll c=karatsubaMultiply(a,b);
bigint res;
res.sign=sign*v.sign;
for(ll i=0,carry=0;i<(ll)c.size();i++){
ll cur=c[i]+carry;
res.a.push_back((ll)(cur%1000000));
carry=(ll)(cur/1000000);
}
res.a=convert_base(res.a,6,base_digits);
res.trim();
return res;
}
};
//INSERT ABOVE HERE
signed main(){
int l;
cin>>l;
if(l==2){
cout<<3<<endl;
cout<<"INF"<<endl;
return 0;
}
cout<<l<<endl;
using M = Matrix<bigint>;
M A(2,2);
A[0][0]=1;A[0][1]=1;
A[1][0]=1;A[1][1]=0;
if(l&1) cout<<A.pow(l)[1][0]<<endl;
else{
auto B=A.pow(l/2);
auto X=M::cross(B,B)[1][0];
auto Y=B[1][0];
cout<<X-Y*Y<<endl;
}
return 0;
}