A. Cat
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#ifdef LOCAL
#define debug(fmt, ...) fprintf(stderr, "[%s] " fmt "\n", __func__, ##__VA_ARGS__)
#define TIME cout << "RunTime: " << clock() << "ms\n", 0
#define DEBUG(...) cout << ">> " << #__VA_ARGS__ << " =", PRT(__VA_ARGS__), cout << endl;
#define DEBUGS(...) cout << ">> " << #__VA_ARGS__ << " =", PRTS(__VA_ARGS__), cout << endl;
void PRT() {}
void PRTS() {}
template <typename S, typename... T>
void PRT(S x, T ... y){
std::cout << " " << x;
PRT(y...);
}
template <typename S>
void PRTS(S x){
for (auto v : x)
std::cout << " " << v;
}
#else
#define debug(...)((void)0) ;
#define DEBUG(...) ((void)0) ;
#define DEBUGS(...) ((void)0) ;
#define TIME 0
#endif
using namespace std;
typedef unsigned long long ll;
const int maxn= 300 + 10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int main(){
#ifdef LOCAL
freopen("/home/acdreams/Desktop/input.txt","r",stdin);
#endif
//cout<<(1000000000000000000-2+1)/2*2+1<<endl;
int t;
scanf("%d",&t);
while(t--){
ll l,r,s;
scanf("%llu%llu%llu",&l,&r,&s);
if(s==0&&l==1&&r<=4&&r>=3)printf("3\n");
else if(s==0&&l==1){
ll L=l,R=r;
if(L%2)L++;
ll res=(R-L+1)/2*2ull;
if(res%4)res++;
res=max(res,(R-L+1)/4*4ull);
if(res==0)printf("-1\n");
else printf("%llu\n",res);
}
else if(s==0){
if(l%2)l++;
if((r-l+1)/4*4ull==0)printf("-1\n");
else printf("%llu\n",(r-l+1)/4*4ull);
}
else if(s==1){
ll L=l,R=r;
if(L%2)L++;
ll res=(R-L+1)/2*2ull;
if(l==1)res++;
if(res==0)printf("-1\n");
else printf("%llu\n",res);
}
else if(s>1){
ll L=l,R=r;
if(L%2)L++;
ll res=(R-L+1)/2*2ull,num=0;
DEBUG(L,R,l,r,res);
if(res%4)num=1;
DEBUG(L,R,l,r,s,res,num);
DEBUG(num^l,num^r,num^l^r);
if(l%2&&(num^l)<=s&&((num^l^r)>s||r%2!=0)){res++;num^=l;}
else if(r%2==0&&(num^r)<=s&&((num^l^r)>s||l%2==0)){res++;num^=r;}
else if(l%2&&r%2==0&&(num^l^r)<=s){res+=2;}
DEBUG(L,R,l,r,s,num);
if(res==0)printf("-1\n");
else printf("%llu\n",res);
}
}
return 0;
}C. <3 numbers
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#ifdef LOCAL
#define debug(fmt, ...) fprintf(stderr, "[%s] " fmt "\n", __func__, ##__VA_ARGS__)
#define TIME cout << "RunTime: " << clock() << "ms\n", 0
#define DEBUG(...) cout << ">> " << #__VA_ARGS__ << " =", PRT(__VA_ARGS__), cout << endl;
#define DEBUGS(...) cout << ">> " << #__VA_ARGS__ << " =", PRTS(__VA_ARGS__), cout << endl;
void PRT() {}
void PRTS() {}
template <typename S, typename... T>
void PRT(S x, T ... y)
{
std::cout << " " << x;
PRT(y...);
}
template <typename S>
void PRTS(S x)
{
for (auto v : x)
std::cout << " " << v;
}
#else
#define debug(...)((void)0) ;
#define DEBUG(...) ((void)0) ;
#define DEBUGS(...) ((void)0) ;
#define TIME 0
#endif
using namespace std;
typedef long long ll;
const int maxn= 1e5+ 10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int check[maxn],p[maxn],tot;
void init(){
check[1]=1;
for(int i=2;i<maxn;++i){
if(!check[i])p[++tot]=i;
for(int j=1;j<=tot&&i*p[j]<maxn;++j){
check[i*p[j]]=1;
if(i*p[j]==0)break;
}
}
check[1]=0;
}
int main(){
#ifdef LOCAL
freopen("/home/acdreams/Desktop/input.txt","r",stdin);
#endif
int t;
scanf("%d",&t);
init();
while(t--){
int l,r;
scanf("%d%d",&l,&r);
if(l>maxn&&r-l+1>3)printf("Yes\n");
else if(r-l+1>=100)printf("Yes\n");
else{
if(r<maxn){
int res=0;
for(int i=l;i<=r;++i){
if(!check[i])res++;
}
if(res*3<r-l+1)printf("Yes\n");
else printf("No\n");
}
else {
int res=0;
for(int i=l;i<=r;++i){
int flag=1;
for(int j=2;1ll*j*j<=i;j++){
if(i%j==0){flag=0;break;}
}
DEBUG(i,flag);
res+=flag;
}
if(res*3<r-l+1)printf("Yes\n");
else printf("No\n");
}
}
}
return 0;
}E. Multiply
题库链接
题意：先给三个数N,X,Y，然后给你N个数a[1...N]，定义Z=a[1]!a[2]!...a[N]!，b[i]=ZX^i ,求最大i满足b[i]是Y!的因子
题解：先利用Pollard_Rho算法log(n)复杂度内分解出X的所有素因子m[1...tot]，然后n*log(n)复杂度内计算出Z含有的素因子m[j]的个数，最后计算y含有多少个因子m[j]，减去Z含有的个数除于X含有的个数，取个最小就是答案
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#ifdef LOCAL
#define debug(fmt, ...) fprintf(stderr, "[%s] " fmt "\n", __func__, ##__VA_ARGS__)
#define TIME cout << "RunTime: " << clock() << "ms\n", 0
#define DEBUG(...) cout << ">> " << #__VA_ARGS__ << " =", PRT(__VA_ARGS__), cout << endl;
#define DEBUGS(...) cout << ">> " << #__VA_ARGS__ << " =", PRTS(__VA_ARGS__), cout << endl;
void PRT() {}
void PRTS() {}
template <typename S, typename... T>
void PRT(S x, T ... y){
std::cout << " " << x;
PRT(y...);
}
template <typename S>
void PRTS(S x){
for (auto v : x)
std::cout << " " << v;
}
#else
#define debug(...)((void)0) ;
#define DEBUG(...) ((void)0) ;
#define DEBUGS(...) ((void)0) ;
#define TIME 0
#endif
using namespace std;
typedef long long ll;
const int maxn=1e5 + 10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
ll Mult_Mod(ll a, ll b, ll m){//res=(a*b)%m
a %= m;
b %= m;
ll res = 0;
while (b){
if (b & 1)
res = (res + a) % m;
a = (a <<= 1) % m;
b >>= 1;
}
return res%m;
}
ll Pow_Mod(ll a, ll b, ll m){//res=(a^b)%m
ll res = 1;
ll k = a;
while (b){
if ((b & 1))
res = Mult_Mod(res, k, m) % m;
k = Mult_Mod(k, k, m) % m;
b >>= 1;
}
return res%m;
}
bool Witness(ll a, ll n, ll x, ll sum){
ll judge = Pow_Mod(a, x, n);
if (judge == n - 1 || judge == 1)
return 1;
while (sum--){
judge = Mult_Mod(judge, judge, n);
if (judge == n - 1)
return 1;
}
return 0;
}
bool Miller_Rabin(ll n){
if (n < 2) return 0;
if (n == 2) return 1;
if ((n & 1) == 0) return 0;
ll x = n - 1;
ll sum = 0;
while (x % 2 == 0){
x >>= 1;
sum++;
}
int times = 50;
for (ll i = 1; i <= times; i++){
ll a = rand() % (n - 1) + 1;//取与p互质的整数a
if (!Witness(a, n, x, sum))//费马小定理的随机数检验
return 0;
}
return 1;
}
ll GCD(ll a, ll b){
return b == 0 ? a : GCD(b, a%b);
}
ll Pollard_Rho(ll n, ll c){//寻找一个因子
ll i = 1, k = 2;
ll x = rand() % n;//产生随机数x0(并控制其范围在1 ~ x-1之间)
ll y = x;
while (1){
i++;
x = (Mult_Mod(x, x, n) + c) % n;
ll gcd = GCD(y - x, n);
if (gcd<0) gcd = -gcd;
if (gcd>1 && gcd < n) return gcd;
if (y == x) return n;
if (i == k){
y = x;
k <<= 1;
}
}
}
ll m[maxn],tot;
void Find_fac(ll n)//对n进行素因子分解，存入factor
{
if (Miller_Rabin(n))//是素数就把这个素因子存起来
{
m[++tot]=n;
return;
}
long long p = n;
while (p >= n)//值变化，防止陷入死循环k
p = Pollard_Rho(p, rand() % (n - 1) + 1);
Find_fac(n / p);
Find_fac(p);
}
//直接Find_fac(n)
ll fac[maxn];
ll fac1[maxn];
ll a[maxn];
ll solve(ll n,ll p){
ll cnt=0;
while(n){
cnt+=n/p;
n/=p;
}
return cnt;
}
ll solve1(ll n,ll p){
ll cnt=0;
while(n%p==0){
cnt++;
n/=p;
}
return cnt;
}
int main(){
#ifdef LOCAL
freopen("/home/acdreams/Desktop/input.txt","r",stdin);
#endif
//cout<<(1000000000000000000-2+1)/2*2+1<<endl;
srand((unsigned)time(NULL));
int t;
//cout<<solve(10,2)<<endl;
scanf("%d",&t);
while(t--){
int N;
ll X,Y;
tot=0;
scanf("%d%lld%lld",&N,&X,&Y);
for(int i=1;i<=N;++i){
scanf("%lld",&a[i]);
}
Find_fac(X); //对X进行素因子分解
sort(m+1,m+1+tot);
tot=unique(m+1,m+1+tot)-m-1; //因子除重
for(int j=1;j<=tot;++j){
fac[j]=0;
fac1[j]=0;
fac1[j]+=solve1(X,m[j]); //求出X含有多少个m[j]
for(int i=1;i<=N;++i){
fac[j]+=solve(a[i],m[j]); //统计a的阶乘乘积含有多少个m[j]
//DEBUG(m[j],a[i],X,fac[j],fac1[j]);
}
}
ll id=0x3f3f3f3f3f3f3f3f; //必须取最值
for(int j=1;j<=tot;++j){
ll res=solve(Y,m[j]); //计算y含有多少个因子m[j];
DEBUG(res,m[j],fac[j],fac1[j]);
id=min(id,(res-fac[j])/fac1[j]); //去比值最小
}
printf("%lld\n",id);
}
return 0;
}F. The Answer to the Ultimate Question of Life, The Universe, and Everything.
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#ifdef LOCAL
#define debug(fmt, ...) fprintf(stderr, "[%s] " fmt "\n", __func__, ##__VA_ARGS__)
#define TIME cout << "RunTime: " << clock() << "ms\n", 0
#define DEBUG(...) cout << ">> " << #__VA_ARGS__ << " =", PRT(__VA_ARGS__), cout << endl;
#define DEBUGS(...) cout << ">> " << #__VA_ARGS__ << " =", PRTS(__VA_ARGS__), cout << endl;
void PRT() {}
void PRTS() {}
template <typename S, typename... T>
void PRT(S x, T ... y)
{
std::cout << " " << x;
PRT(y...);
}
template <typename S>
void PRTS(S x)
{
for (auto v : x)
std::cout << " " << v;
}
#else
#define debug(...)((void)0) ;
#define DEBUG(...) ((void)0) ;
#define DEBUGS(...) ((void)0) ;
#define TIME 0
#endif
using namespace std;
typedef long long ll;
const int maxn= 1e5+ 10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
unordered_map<ll,int>mp;
int a[300]={-5000,-5000,-4373,-5,-5001,-5001,-637,-169,-5000,-216,-650,-695,-11,-5001,-5001,-265,-4114,-3331,-1373,-95,-2816,-401,-5001,-5001,-10,-2683,-2107,-5000,-2268,-233,-5001,-5001,-5001,-5001,-1555,-1120,-3223,-444,-27,-5001,-5001,-5001,-5001,-823,-7,-2369,-758,-141,-3950,-5001,-5001,-796,-5001,-2370,-3885,-3329,-672,-998,-5001,-5001,-1201,-966,-2744,-161,-5000,-929,1,-5001,-5001,-403,-2359,-533,-432,-335,-5001,-5001,-5001,-5001,-2080,-706,-1300,-2368,-1317,-3707,-5001,-5001,-5001,-4126,-1390,-2514,-1803,-3389,-4052,-248,-5001,-5001,-22,-3168,-2101,-893,-1797,-2327,-239,-5001,-5001,-7,-2689,-1309,-1165,-2948,-5001,-4793,-5001,-5001,-5001,-12,-1906,-896,-4328,-3677,-2804,-5001,-5001,-37,-1,-5000,-2212,-4034,-3989,-1580,-5001,-5001,-1,-399,-3013,-1351,-1116,-758,-86,-5001,-5001,-139,-7,-5001,-2746,-8,-327,-2366,-5001,-5001,-367,-463,-805,-3736,-2135,-3693,-5001,-5001,-5001,-1534,-3874,-4767,-4125,-3423,-66,-5001,-5001,-5001,-802,-1354,-3834,-1328,-5001,-5001,-335,-5001,-5001,-1168,-13,-2839,-5001,-4874,-90,-4889,-5001,-5001,-4,-1885,-1639,-1702,-4812,-377,-20,-5001,-5001,-5001,-1057,-2867,-3752,-2208,-2318};
int b[300]={0,1,-486,4,0,0,-205,44,2,-52,-353,-641,7,0,0,-262,-588,2195,-1276,47,-741,-287,0,0,8,1839,237,3,-249,-69,0,0,0,0,-244,-509,2358,-84,16,0,0,0,0,-307,-5,1709,-473,49,-1247,0,0,602,0,1518,-648,1837,505,361,0,0,-163,668,-1561,102,4,403,1,0,0,134,824,401,-104,-146,0,0,0,0,-829,-196,-706,-1719,847,1315,0,0,0,-1972,-1282,1953,365,-2912,861,-98,0,0,14,-991,-1638,-622,-903,319,118,0,0,-4,-1165,947,-948,853,0,-2312,0,0,0,8,-757,-555,383,-1673,1219,0,0,-16,0,5,-419,-3881,-726,-1238,0,0,2,167,-1766,-629,816,-428,-77,0,0,104,-3,0,-2552,-7,-263,1528,0,0,260,215,486,-695,-516,-1049,0,0,0,383,-1654,-2476,-1417,-2943,-59,0,0,0,-574,-1012,-2149,891,0,0,-170,0,0,-160,-10,1503,0,974,-29,976,0,0,5,-1092,318,-1403,-593,-215,16,0,0,0,-579,-1606,-1347,508,-638};
int c[300]={5000,5000,4375,4,0,0,644,168,5000,217,683,843,10,0,0,332,4118,2977,1671,91,2833,445,0,0,8,2357,2106,5000,2269,235,0,0,0,0,1557,1154,2731,445,25,0,0,0,0,837,8,2025,815,139,3991,0,0,659,0,2141,3891,3131,559,982,0,0,1202,845,2903,146,5000,903,4,0,0,398,2325,443,434,344,0,0,0,0,2123,711,1366,2638,1188,3651,0,0,0,4271,1686,2036,1798,3992,4039,253,0,0,20,3200,2391,984,1870,2325,229,0,0,8,2760,1117,1345,2924,0,4966,0,0,0,11,1945,962,4327,3789,2725,0,0,38,5,5000,2217,4988,3997,1801,0,0,5,389,3203,1395,946,801,103,0,0,116,8,0,3342,10,376,2131,0,0,317,447,741,3744,2145,3721,0,0,0,1526,3972,4980,4180,4033,79,0,0,0,890,1521,4047,1178,0,0,349,0,0,1169,15,2691,0,4861,91,4876,0,0,5,2000,1635,1974,4815,399,16,0,0,0,1112,3026,3809,2199,2334};
int main(){
#ifdef LOCAL
//freopen("/home/acdreams/Desktop/ouput.txt","r",stdin);
//freopen("/home/acdreams/Desktop/ouput1.txt","w",stdout);
#endif
// for(int i=-5000;i<=5000;++i)mp[1ll*i*i*i]=i;
// for(int x=0;x<=200;++x){
// int flag=0;
// for(int a=-5000;a<=5000;++a){
// for(int b=-5000;b<=5000;++b){
// if(mp.count(1ll*x-(1ll*a*a*a)-1ll*b*b*b)){
// cout<<x<<" "<<a<<" "<<b<<" "<<mp[1ll*x-1ll*a*a*a-1ll*b*b*b]<<endl;
// flag=1;
// break;
// }
// }
// if(flag)break;
// }
// if(!flag)cout<<x<<" "<<-1<<endl;
// }
//124 132
// for(int i=0;i<=200;i++)
// {
// int x;
// scanf("%d",&x);
//
// int aa,bb,cc;
// scanf("%d",&aa);
// if(aa==-1 && (i!=124 && i!=132))
// a[i]=-5001;
// else{
// a[i]=aa;
// scanf("%d%d",&b[i],&c[i]);
// }
// }
// printf("a[300]={");
// for(int i=0;i<=200;i++){
// printf("%d,",a[i]);
// }
// printf("}\n");
// printf("b[300]={");
// for(int i=0;i<=200;i++){
// printf("%d,",b[i]);
// }
// printf("}\n");
// printf("c[300]={");
// for(int i=0;i<=200;i++){
// printf("%d,",c[i]);
// }
// printf("}\n");
int t;
scanf("%d",&t);
while(t--){
int x;
scanf("%d",&x);
if(a[x]==-5001)
printf("impossible\n");
else
printf("%d %d %d\n",a[x],b[x],c[x]);
}
return 0;
}M. Kill the tree
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#ifdef LOCAL
#define debug(fmt, ...) fprintf(stderr, "[%s] " fmt "\n", __func__, ##__VA_ARGS__)
#define TIME cout << "RunTime: " << clock() << "ms\n", 0
#define DEBUG(...) cout << ">> " << #__VA_ARGS__ << " =", PRT(__VA_ARGS__), cout << endl;
#define DEBUGS(...) cout << ">> " << #__VA_ARGS__ << " =", PRTS(__VA_ARGS__), cout << endl;
void PRT() {}
void PRTS() {}
template <typename S, typename... T>
void PRT(S x, T ... y)
{
std::cout << " " << x;
PRT(y...);
}
template <typename S>
void PRTS(S x)
{
for (auto v : x)
std::cout << " " << v;
}
#else
#define debug(...)((void)0) ;
#define DEBUG(...) ((void)0) ;
#define DEBUGS(...) ((void)0) ;
#define TIME 0
#endif
using namespace std;
typedef long long ll;
const int maxn= 2e5 + 10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
vector<int> e[maxn];
int pre[maxn],ans[maxn],ans1[maxn];
int sz[maxn];
void dfs(int x,int f){
pre[x]=f;
sz[x]=1;
int mx=0,mk=-1;
for(auto v:e[x]){
if(v!=f){
dfs(v,x);
sz[x]+=sz[v];
if(mx<sz[v])
mx=sz[v],mk=v;
}
}
if(mk==-1){
ans[x]=x;
return;
}
ans[x]=ans[mk];
while((sz[x]-sz[ans[x]])*2>sz[x]){
//cout<<sz[x]<<" "<<sz[ans[x]]<<endl;
ans[x]=pre[ans[x]];
}
if( ((sz[x]-sz[ans[x]])*2 == sz[x]) )ans1[x]=pre[ans[x]];
}
int main()
{
#ifdef LOCAL
freopen("/home/acdreams/Desktop/input.txt","r",stdin);
#endif
int n;
scanf("%d",&n);
for(int i=1;i<n;i++){
ans1[i]=-1;
int u,v;
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
ans1[n]=-1;
dfs(1,1);
for(int i=1;i<=n;i++){
// cout<<i<< ' '<<sz[i]<<endl;
if(ans1[i]==-1)
printf("%d\n",ans[i]);
else{
int a=ans1[i],b=ans[i];
if(a>b)swap(a,b);
printf("%d %d\n",a,b);
}
}
return 0;
}
2 条评论
题目待补 J L