11.29T3

dw_dz · 2025-11-29 19:36:16 · 生活·游记

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,fib[100],ans;bool vis[100000000];
void dfs(int x2,int x3,int x8,int x144) {
    if(vis[x2*1000000+x3*10000+x8*100+x144]) return;
    ans++;vis[x2*10000000+x3*10000+x8*100+x144]=1;
    if(x2>=3) dfs(x2-3,x3,x8+1,x144);
    if(x2>=1&&x3>=2&&x8>=1) dfs(x2-1,x3-2,x8-1,x144+1);
}
void work() {
    cin>>n;ans=0;
    int s2=0,s3=0;
    for(int i=85;i>=3;i--) {
        if(fib[i]==8||fib[i]==144) continue;
        while(n%fib[i]==0) n/=fib[i];
    }
    while(n%2==0) n/=2,s2++;
    while(n%3==0) n/=3,s3++;
    if(n>1){cout<<"0\n";return;}
    dfs(s2,s3,0,0);cout<<ans<<"\n";
}
signed main() {
    freopen("fibonacci.in","r",stdin);
    freopen("fibonacci.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    for(int a=1,b=2,i=1;b<=1e18;i++) {
        fib[i]=b;int t=a+b;a=b;b=t;
    }int T;cin>>T;while(T--) work();
}

完了,突然发现我多测没清空vis数组\ 大样例过了,小样例没过