2019icpc徐州站 [Cloned]
A-Cat
B-Cats line up
C-< 3 numbers
题意：
给你一个l，r的区间，问[l，r]区间内因子个数小于3的数的个数与区间长度的比值是否小于三分之一，如果是，输出yes，否则，输出no
solution：
先算出l到r内质数的个数，有个板子。然后特判区间包含1的情况，因为1的因子个数也是小于3 的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
ll check(ll v,ll n,ll ndr,ll nv){
return v>=ndr?(n/v-1):(nv-v);
}
ll primenum(ll n)
{
ll r=(ll)sqrt(n);
ll ndr=n/r;
assert(r*r<=n&&(r+1)*(r+1)>n);
ll nv=r+ndr-1;
std::vector<ll>S(nv+1);
std::vector<ll>V(nv+1);
for(ll i=0;i<r;i++){
V[i]=n/(i+1);
}
for(ll i=r;i<nv;i++){
V[i]=V[i-1]-1;
}
for(ll i=0;i<nv;i++){
S[i]=V[i]-1;
}
for(ll p=2;p<=r;p++){
if(S[nv-p]>S[nv-p+1]){
ll sp=S[nv-p+1];
ll p2=p*p;
for(ll i=0;i<nv;i++){
if(V[i]>=p2){
S[i]-=1ll*(S[check(V[i]/p,n,ndr,nv)]-sp);
}
else break;
}
}
}
return S[0];
}
int l,r;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&l,&r);
ll res=0;
if(l>1)
res=primenum(r)-primenum(l-1);
if(l<=1)res=primenum(r)+1;
if(res*3<r-l+1)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
D-Polycut
E-Multiply
题意：
给你N，X，Y，以及长度为n的数组ai，给了下图的式子
让你求最大的i是多少。
solution:
先将X分解成一堆素数相乘
那么对应于X的这些素数，Y！可以分解成对应的素数相乘，X中没出现的素数可以舍去，这里用？代替。
先引出一个定理：n的阶乘中p的幂次为
同理，对于ai！也可以这样处理。
这样就可以知道对于每个素数X中有几个，Y！中有几个，ai！中有几个，最后只要对应素数在Y！的个数减去在ai！中个数的综合再除以在X中的个数取个min就是答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int C=2307;
const int S=10;
typedef pair<ll,int>pli;
mt19937 rd(time(0));
vector<ll>ve;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;}
ll mul(ll a,ll b,ll mod){
return (__int128)a*b%mod;}
ll power(ll a,ll b,ll mod){
ll res=1;a%=mod;
while(b){
if(b&1)res=mul(res,a,mod);
a=mul(a,a,mod);
b>>=1;
}
return res;
}
bool check(ll a,ll n){
ll m=n-1,x,y;
int j=0;
while(!(m&1))m>>=1,j++;
x=power(a,m,n);
for(int i=1;i<=j;x=y,i++){
y=mul(x,x,n);
if(y==1&&x!=1&&x!=n-1)return 1;
}
return y!=1;
}
bool miller_rabin(ll n){
ll a;
if(n==1)return 0;
if(n==2)return 1;
if(!(n&1))return 0;
for(int i=0;i<S;i++)if(check(rd()%(n-1)+1,n))return 0;
return 1;
}
ll pollard_rho(ll n,ll c){
ll i=1,k=2,x=rd()%n,y=x,d;
while(1){
i++;x=(mul(x,x,n)+c)%n,d=gcd(y-x,n);
if(d>1&&d<n)return d;
if(y==x)return n;
if(i==k)y=x,k<<=1;
}
}
void findfac(ll n,int c){
if(n==1)return;
if(miller_rabin(n)){
ve.push_back(n);
return;
}
ll m=n;
while(m==n)m=pollard_rho(n,c--);
findfac(m,c);
findfac(n/m,c);
}
vector<pli> solve(ll n){
vector<pli>res;
ve.clear();
findfac(n,C);
sort(ve.begin(),ve.end());
for(auto x:ve){
if(res.empty()||res.back().first!=x)res.push_back({
x,1});
else res.back().second++;
}
return res;
}
int T;
ll x,y;
int n;
ll a[100005];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%lld%lld",&n,&x,&y);
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
vector<pli> res=solve(x);
ll minn=INF;
//cout<<res.size();
for(auto p:res)
{
ll q=0;
ll tem=y;
while(tem)
{
q+=tem/p.first;
tem/=p.first;
}
for(int i=0;i<n;i++)
{
ll qq=0;
tem=a[i];
while(tem)
{
qq+=tem/p.first;
tem/=p.first;
}
q-=qq;
}
//printf("%lld %d %lld\n",p.first,p.second,q);
minn=min(minn,q/p.second);
}
printf("%lld\n",minn);
}
return 0;
}
F-The Answer to the Ultimate Question of Life, The Universe, and Everything.
题意：
根据所给的x，求出
的一个方案，输出a，b，c的值
solution：
我是暴力打表过的，先求出在小范围内算出答案，再扩大范围算出在小范围内无解的答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int t,x;
string s[210];
int main()
{
s[0]="-100 0 100";
s[1]="-100 1 100";
s[2]="-47 -24 49";
s[3]="-5 4 4";
s[4]="impossible";
s[5]="impossible";
s[6]="-58 -43 65";
s[7]="-1 0 2";
s[8]="-100 2 100";
s[9]="0 1 2";
s[10]="-3 -3 4";
s[11]="-2 -2 3";
s[12]="-11 7 10";
s[13]="impossible";
s[14]="impossible";
s[15]="-46 23 44";
s[16]="-94 -48 98";
s[17]="-52 25 50";
s[18]="-2 -1 3";
s[19]="-95 47 91";
s[20]="-56 21 55";
s[21]="-86 28 85";
s[22]="impossible";
s[23]="impossible";
s[24]="-10 8 8";
s[25]="-1 -1 3";
s[26]="-1 0 3";
s[27]="-100 3 100";
s[28]="-59 31 56";
s[29]="-20 13 18";
s[30]="impossible";
s[31]="impossible";
s[32]="impossible";
s[33]="impossible";
s[34]="-6 5 5";
s[35]="-13 -8 14";
s[36]="-75 40 71";
s[37]="-56 37 50";
s[38]="-27 16 25";
s[39]="impossible";
s[40]="impossible";
s[41]="impossible";
s[42]="impossible";
s[43]="-52 20 51";
s[44]="-7 -5 8";
s[45]="-3 2 4";
s[46]="-29 19 26";
s[47]="-50 -50 63";
s[48]="-26 -23 31";
s[49]="impossible";
s[50]="impossible";
s[51]="602 659 -796";
s[52]="impossible";
s[53]="-4 -2 5";
s[54]="-18 -15 21";
s[55]="-23 -23 29";
s[56]="-47 31 42";
s[57]="-38 25 34";
s[58]="impossible";
s[59]="impossible";
s[60]="-4 -1 5";
s[61]="-4 0 5";
s[62]="-43 22 41";
s[63]="-63 -37 67";
s[64]="-100 4 100";
s[65]="0 1 4";
s[66]="1 1 4";
s[67]="impossible";
s[68]="impossible";
s[69]="-22 -19 26";
s[70]="-64 23 63";
s[71]="-33 -22 36";
s[72]="-27 -13 28";
s[73]="-47 29 43";
s[74]="impossible";
s[75]="impossible";
s[76]="impossible";
s[77]="impossible";
s[78]="-55 26 53";
s[79]="-66 -49 74";
s[80]="-6 -6 8";
s[81]="-18 10 17";
s[82]="-11 -11 14";
s[83]="-36 -32 43";
s[84]="impossible";
s[85]="impossible";
s[86]="impossible";
s[87]="-4126 4271 -1972";
s[88]="-16 -9 17";
s[89]="-7 6 6";
s[90]="-100 31 99";
s[91]="-5 0 6";
s[92]="-8 -5 9";
s[93]="-5 -5 7";
s[94]="impossible";
s[95]="impossible";
s[96]="-22 14 20";
s[97]="-22 17 18";
s[98]="-15 9 14";
s[99]="-37 16 36";
s[100]="-6 -3 7";
s[101]="-83 46 78";
s[102]="-239 118 229";
s[103]="impossible";
s[104]="impossible";
s[105]="-7 -4 8";
s[106]="-19 -19 24";
s[107]="-48 -28 51";
s[108]="-1165 1345 -948";
s[109]="-44 -18 45";
s[110]="impossible";
s[111]="-4793 4966 -2312";
s[112]="impossible";
s[113]="impossible";
s[114]="impossible";
s[115]="-12 8 11";
s[116]="-2 -1 5";
s[117]="-2 0 5";
s[118]="-99 76 81";
s[119]="-14 -8 15";
s[120]="-92 46 88";
s[121]="impossible";
s[122]="impossible";
s[123]="-37 -16 38";
s[124]="-1 0 5";
s[125]="-100 5 100";
s[126]="-12 -7 13";
s[127]="-11 9 9";
s[128]="-77 -54 85";
s[129]="1 4 4";
s[130]="impossible";
s[131]="impossible";
s[132]="-1 2 5";
s[133]="-91 -37 93";
s[134]="-91 49 86";
s[135]="-28 -17 30";
s[136]="2 4 4";
s[137]="-30 -23 34";
s[138]="-86 -77 103";
s[139]="impossible";
s[140]="impossible";
s[141]="-19 -10 20";
s[142]="-7 -3 8";
s[143]="impossible";
s[144]="-72 -25 73";
s[145]="-8 -7 10";
s[146]="-9 -5 10";
s[147]="-56 -50 67";
s[148]="impossible";
s[149]="impossible";
s[150]="-367 260 317";
s[151]="-4 -1 6";
s[152]="-32 -28 38";
s[153]="-15 11 13";
s[154]="-6 3 7";
s[155]="-68 24 67";
s[156]="impossible";
s[157]="impossible";
s[158]="impossible";
s[159]="-130 80 119";
s[160]="-76 -51 83";
s[161]="-31 20 28";
s[162]="-21 -14 23";
s[163]="-76 -68 91";
s[164]="-66 -59 79";
s[165]="impossible";
s[166]="impossible";
s[167]="impossible";
s[168]="-28 -22 32";
s[169]="-7 0 8";
s[170]="-38 23 35";
s[171]="-87 67 71";
s[172]="impossible";
s[173]="impossible";
s[174]="-41 31 34";
s[175]="impossible";
s[176]="impossible";
s[177]="-7 2 8";
s[178]="-13 -10 15";
s[179]="-4 3 6";
s[180]="impossible";
s[181]="-59 -32 62";
s[182]="-90 -29 91";
s[183]="-17 10 16";
s[184]="impossible";
s[185]="impossible";
s[186]="-4 5 5";
s[187]="-58 27 56";
s[188]="-74 -55 83";
s[189]="-63 -29 65";
s[190]="-89 36 87";
s[191]="-80 63 64";
s[192]="-20 16 16";
s[193]="impossible";
s[194]="impossible";
s[195]="impossible";
s[196]="-34 -15 35";
s[197]="-10 -10 13";
s[198]="-48 -19 49";
s[199]="-73 -47 79";
s[200]="-2 -2 6";
/*for(int i=0;i<=200;i++) { bool flag=true; if(s[i]=="impossible") { for(int j=-5000;j<=5000;j++) { for(int k=-5000;k<=5000;k++) { ll w=pow(abs(1ll*j*j*j+1ll*k*k*k-x),1.0/3); if(1ll*j*j*j+1ll*k*k*k-x>0)w=-w; if(i==1ll*j*j*j+1ll*k*k*k+1ll*w*w*w) { printf("s[%d]=\"%d %d %d\"\n",i,j,k,w); flag=false; break; } if(!flag)break; } if(!flag)break; } if(flag) printf("s[%d]=\"impossible\"\n",i); } }*/
cin>>t;
while(t--)
{
cin>>x;
cout<<s[x]<<endl;
}
return 0;
}
拼多多集团-PDD公司氛围 520人发布