求调div3C

_Delete_ @ 2024-03-10 18:06:40

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//value 
struct ex{
    ll mo,da;
}ans[50005];
ll a[300005];

//function 
bool cmp(ex a,ex b){
    if(a.mo==b.mo)return a.da<b.da;
    return a.mo<b.mo;
}
void solve(){

    ll n,k;
    ll ma=-1,wz=-1;
    cin>>n>>k;
    for(ll i=0;i<n;i++)cin>>a[i];
    if(k==1){
        cout<<0<<endl;
        return;
    }
    ll tmp=0;
    ll q=k;
//  cout<<wz<<' '<<ma<<endl;
//  cout<<(ll)wz*ma+a[wz]<<endl;
    while(k<100000000000){
//      if(k==124)cout<<k<<endl;
        if(k<=10){
            k*=q;
            continue;
        }
        ll cnt=1;
        while(k/cnt>0)cnt*=10;
//      cnt/=10;
        for(ll i=1;i<cnt;i*=10){
            ll m=k/i,d=k%i;
            ll w=1;
            while(d/w>0)w*=10;
            if(m*w+d!=k)continue;
            if(m>n)continue;
            else if(d>a[m-1])continue;
            else{
                ans[tmp].mo=m;
                ans[tmp++].da=d;
            }
        }
        k*=q;
    }

    if(tmp==0){
        cout<<0<<endl;
        return;
    }
    sort(ans,ans+tmp,cmp);

    cout<<tmp<<endl;
    for(ll i=0;i<tmp;i++){
        cout<<ans[i].mo<<' '<<ans[i].da<<endl;
        ans[i].mo=0;
        ans[i].da=0;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); 

    int T;
    cin>>T;
    while(T--)solve();

    return 0;
}

by wangyizhi @ 2024-03-10 18:10:08

强烈建议把k开__int128

by Kayisama @ 2024-03-10 18:35:41

看不懂，这是我的AC代码

#include <bits/stdc++.h>
using namespace std;
namespace MySpace{
    #define max(...) MyDearmax(__VA_ARGS__)
    template <typename T>
    T MyDearmax(T a, T b) {return a > b ? a : b;}
    template <typename F, typename... R>
    F MyDearmax(F f,R... r){return MyDearmax(f,MyDearmax(r...));}
    #define min(...) MyDearmin(__VA_ARGS__)
    template <typename T>
    T MyDearmin(T a, T b) {return a < b ? a : b;}
    template <typename F, typename... R>
    F MyDearmin(F f,R... r){return MyDearmin(f,MyDearmin(r...));}
    #define lowbit(x) (x&(-x))
    #define sqrt __builtin_sqrtf //使用硬件加速的开方
    #ifdef ONLINE_JUDGE
    #define getchar getchar_unlocked
    #endif
    inline void read() {}
    template <typename T, typename... R>
    inline void read(T &x,R &... oth){
        x=0;T f=1;
        char c=getchar();
        while(c<'0' || c>'9') {
            if(c=='-') f=-1;
            c=getchar();
        }
        while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
        x*=f;
        read(oth...);
        return;
    }
    template<typename T>
    T qpow(T a,T n,T p){
        T res=1;
        while (n){
            if (n&1) res=1ll*res*a%p;
            a=1ll*a*a%p;
            n>>=1;
        }
        return res;
    }
    template<typename T>
    T gcd(T a,T b){return (b>0?gcd(b,a%b):a);}
    template<typename T>
    T exgcd(T a,T b,T& x,T& y){
        if (b<=0ll){
            x=1ll,y=0ll;
            return a;
        }
        T t=x;
        T d=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return d;
    }
    template<typename T>
    T inv(T a,T p){
        if (a==1) return 1ll;
        T x,y;
        if (exgcd(a,p,x,y)!=1ll) return -1ll;
        else return (x+p)%p;
    }
}
using namespace MySpace;
//const int INF=0x66CCFF66;
#define int long long
const int maxn=3e5+5;
int T;
int n,k,kkk;
int a[maxn];
using pi=pair<int,int>;
vector<pi> ans;
int getnum(int a,int b){
    int t=10;
    for (;b>t;t*=10);
    return a*t+b;
}
void check(int k){
    for (int t=10;k>t;t*=10){
        int fr=k/t,ta=k%t;
        if (k%(t/10)==ta) continue;
        if (fr<1 || fr>n) continue;
        if (ta>=1 && ta<=a[fr]) 
            ans.push_back(make_pair(fr,ta));
    }
    return;
}
signed main(){
    read(T);
    while (T--){
        while (!ans.empty()) ans.pop_back();
        memset(a,0,sizeof a);
        read(n,k);
        for (int i=1;i<=n;i++) read(a[i]);
        if (k<=1) {
            printf("0\n");
            continue;
        }
        kkk=k;
        int maxx=0;
        for (int i=1;i<=n;i++)
            maxx=max(maxx,getnum(i,a[i]));
        if (k>=10) check(k);
        while (k<=maxx/kkk){
            k*=kkk;
            if (k>=10) check(k);
        }
        printf("%lld\n",ans.size());
        stable_sort(ans.begin(),ans.end(),[](pi a,pi b){
            if (a.first==b.first) return a.second<b.second;
            else return a.first<b.first;
        });
        for (auto t:ans)
            printf("%lld %lld\n",t.first,t.second);
    }
    return 0;
}