QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#816675 | #9705. Multiply | N_z_ | WA | 1ms | 3812kb | C++23 | 7.8kb | 2024-12-16 16:29:31 | 2024-12-16 16:29:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct time_helper{
#ifdef LOCAL
clock_t time_last;time_helper(){time_last=clock();}void test(){auto time_now=clock();std::cerr<<"time:"<<1.*(time_now-time_last)/CLOCKS_PER_SEC<<";all_time:"<<1.*time_now/CLOCKS_PER_SEC<<std::endl;time_last=time_now;}~time_helper(){test();}
#else
void test(){}
#endif
}time_helper;
#ifdef LOCAL
#include"dbg.h"
#else
#define dbg(...) (__VA_ARGS__)
#endif
namespace Fread{const int SIZE=1<<16;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}namespace Fwrite{const int SIZE=1<<16;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}
#define getchar Fread::getchar
#define putchar Fwrite::putchar
int print_precision=10;bool print_T_endl=1;char print_between=' ';
template<typename T>struct is_char{static constexpr bool value=(std::is_same<T,char>::value||std::is_same<T,signed char>::value||std::is_same<T,unsigned char>::value);};template<typename T>struct is_integral_ex{static constexpr bool value=(std::is_integral<T>::value||std::is_same<T,__int128>::value)&&!is_char<T>::value;};template<typename T>struct is_floating_point_ex{static constexpr bool value=std::is_floating_point<T>::value||std::is_same<T,__float128>::value;};namespace Fastio{struct Reader;struct Writer;template<size_t id>struct read_tuple{template<typename...T>static void read(Reader&stream,std::tuple<T...>&x){read_tuple<id-1>::read(stream,x);stream>>get<id-1>(x);}};template<>struct read_tuple<0>{template<typename...T>static void read([[maybe_unused]]Reader&stream,[[maybe_unused]]std::tuple<T...>&x){}};template<size_t id>struct print_tuple{template<typename...T>static void print(Writer&stream,const std::tuple<T...>&x){print_tuple<id-1>::print(stream,x);putchar(print_between);stream<<get<id-1>(x);}};template<>struct print_tuple<1>{template<typename...T>static void print(Writer&stream,const std::tuple<T...>&x){stream<<get<0>(x);}};template<>struct print_tuple<0>{template<typename...T>static void print([[maybe_unused]]Writer&stream,[[maybe_unused]]const std::tuple<T...>&x){}};
struct Reader{template<typename T>typename std::enable_if_t<std::is_class<T>::value,Reader&>operator>>(T&x){for(auto &y:x)*this>>y;return *this;}template<typename...T>Reader&operator>>(std::tuple<T...>&x){read_tuple<sizeof...(T)>::read(*this,x);return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1;while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;return *this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1,s=0;x=0;T t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Reader&>operator>>(T&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}template<typename T1,typename T2>Reader&operator>>(std::pair<T1,T2>&x){*this>>x.first>>x.second;return *this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';
struct Writer{typedef __int128 mxdouble;template<typename T>typename std::enable_if_t<std::is_class<T>::value,Writer&>operator<<(const T&x){for(auto q:x){*this<<q;if(!is_class<decltype(q)>::value)*this<<print_between;}if(!is_class<typename T::value_type>::value&&print_T_endl)*this<<'\n';return *this;}template<typename...T>Writer&operator<<(const std::tuple<T...>&x){print_tuple<sizeof...(T)>::print(*this,x);if(print_T_endl)*this<<'\n';return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Writer&>operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Writer&>operator<<(T x){if(x<0)putchar('-'),x=-x;x+=pow(10,-print_precision)/2;mxdouble _=x;x-=(T)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<print_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<print_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Writer&>operator<<(const T&c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}template<typename T1,typename T2>Writer&operator<<(const std::pair<T1,T2>&x){*this<<x.first<<print_between<<x.second;if(print_T_endl)*this<<'\n';return *this;}Writer&operator<<(const std::string&str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
template<class Fun>class y_combinator_result{Fun fun_;public:template<class T>explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}template<class ...Args>decltype(auto) operator()(Args &&...args){return fun_(std::ref(*this), std::forward<Args>(args)...);}};template<class Fun>decltype(auto) y_combinator(Fun &&fun){return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));}
void init();void solve(int tc);
signed main()
{
init();int t=1;
cin>>t;
for(int tc=1;tc<=t;tc++)solve(tc);
}
void init()
{
}
namespace PR{typedef long long ll;typedef __int128 lll;const int N=9,P=1<<7;int test_prime[N+1]={0,2,3,5,7,11,13,17,19,23};ll gcd(ll a,ll b){if(!a||!b)return a|b;int az=__builtin_ctzll(a);int bz=__builtin_ctzll(b);int z=min(az,bz);b>>=bz;while(a){a>>=az;ll diff=a-b;az=__builtin_ctzll(diff);b=min(a,b),a=abs(diff);}return b<<z;}inline ll quick_pow(ll x,ll p,ll mod){ll ans=1;while(p){if(p&1)ans=(lll)ans*x%mod;x=(lll)x*x%mod;p>>=1;}return ans;}inline bool is_prime(ll n){if(n<2)return false;int cnt=0;ll m=n-1,k=m;while(k%2==0){k/=2;cnt++;}for(int i=1;i<=N;i++){if(n==test_prime[i])return true;ll a=quick_pow(test_prime[i],k,n),b=a;for(int j=1;j<=cnt;j++){b=(lll)b*a%n;if(b==1&&a!=1&&a!=m)return false;a=b;}if(a!=1)return false;}return true;}inline ll floyd(ll a,ll b,ll p){return ((lll)a*a%p+b)%p;}inline ll abs64(ll n){return n>=0?n:-n;}mt19937 mt(random_device{}());inline ll pollard_pho(ll n){ll x=0,c=mt()%(n-1)+1;for(int i=1;;i<<=1){ll y=1,z=x;for(int j=1;j<=i;j++){x=floyd(x,c,n);y=(lll)y*abs64(x-z)%n;if(j==i||j%P==0){ll ans=gcd(n,y);if(ans>1)return ans;}}}}map<ll,int>mp;void decompound_(ll n){if(n<2)return;if(is_prime(n)){mp[n]++;return;}ll factor;do{factor=pollard_pho(n);}while(factor==n);decompound_(factor);decompound_(n/factor);}map<ll,int>decompound(ll n){mp.clear();decompound_(n);return mp;}}
void solve([[maybe_unused]]int tc)
{
int n;
long long u,v;
cin>>n>>u>>v;
vector<long long>a(n);
cin>>a;
long long ans=1e18;
auto cnt=[&](long long a,long long b)
{
long long res=0;
while(a)res+=(a/=b);
return res;
};
for(auto [q,c]:PR::decompound(u))
{
long long nc=cnt(v,q);
for(auto w:a)nc-=-cnt(w,q);
ans=min(ans,nc/c);
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
2 3 10 10 2 3 4 2 2 10 1 1
output:
2 8
result:
ok 2 number(s): "2 8"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3812kb
input:
8 929 98210021061137 164832982985885580 43576998167336 157303878397705 212661169553039 169068044677212 17733912750082 101059786177542 56528418806042 170741049344189 128297164019222 208810463591190 96264177952672 70816863413347 116985928070432 56330014332760 10006522486360 110959002803542 15298525649...
output:
2297 939471396 5628474751732 49490737759721 1012040435295869 219959966197308892 12700578092686100 3842971587795855
result:
wrong answer 1st numbers differ - expected: '1059', found: '2297'