A题不解释,不过所有题目在这里

hdu 6264 <http://acm.hdu.edu.cn/showproblem.php?pid=6264>

B题 Master of Phi

hdu 6265 <http://acm.hdu.edu.cn/showproblem.php?pid=6265>


题意:有T个数据,模数是998244353,每个数据输入一个m,然后m行每行输入一个pi,qi,其中每个pi都是质数且不重复,表示pi的qi次方,最后把每个pi的qi次方相乘得到一个n,求n的每一个因数的(欧拉函数*n/这个因数)的和,输出它们的和。

分享一个wa了的思路,感觉没毛病,如果有大神发现其bug,求指教,万分感谢。


思路:先把每一个加数的n提出来,用f(x)表示x的欧拉函数,pow(x,y)表示x的y次方,G(x)表示f(x)/x,因为pi都是质数,所以f(pow(pi,qi))=pow(pi,qi)*(1-1/pi),G(f(pow(pi,qi)))=(1-1/pi),而且得出来的值和qi无关,那么pi和qi可以组成n的几个因数呢,不难发现除1以外可以组成qi个因数,又因为G(*)的值与qi无关,得出sum(G(f(pow(pi,i))))|i=1,2...qi=(1-1/pi)*qi=qi-qi/pi,把sum(G(f(pow(pi,i))))|i=1,2,..qi当做ai,那么m对pi,qi就是有m个ai,n的所有因数的G()的值就ai的自由组合,即求a1,a2,a1a2,a3,a1a3,a1a2a3,.....,a1a2a3..am的和,可以用dfs或者递推,递推思路就是所有以ai结尾的项之和等于所有以a(i-1)结尾的项之和+1再乘以ai。

/*****续更,给p[i ],q[ i ]赋值时用long long 赋值: scanf("%lld%lld",&p[ i ],&q[ i
])就ac了....赋值没注意,wa了我好几天,经验还是不足啊
#include<stdio.h> long long mod=998244353; long long ans; long long
chengfang(long long a,int n) { long long ans=1; while(n>0)//快速幂 { if(n%2==1)
ans=ans*a%mod; a=a*a%mod; n/=2; } return ans%mod; } void dfs(int k,long long
a[30],long long sum,int m) { if(k>m) { ans=(ans+sum)%mod; return; } long long
sum1=sum*a[k]%mod; dfs(k+1,a,sum1,m); dfs(k+1,a,sum,m); } int main() { int T;
scanf("%d",&T); while(T--) { int i,m; long long p[30],q[30]; long long a[30];
long long n=1; scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d%d",&p[i],&q[i]);
//scanf("%lld%lld",&p[i],&q[i]); 改成这样就ac,竟然在这个地方掉坑,丢脸啊...
a[i]=(q[i]+mod-(q[i]*chengfang(p[i],mod-2)%mod))%mod;//费马小定理求逆元
n=n*chengfang(p[i],q[i])%mod; } ans=0; long long sum[30]={0}; for(i=1;i<=m;i++)
{ sum[i]=((ans+1)%mod)*(a[i]%mod)%mod; ans=(ans+sum[i])%mod; } ans++;//最后加上一个1
//dfs(1,a,1,m); printf("%lld\n",(ans*n)%mod); } }
 

C题 Hakase and Nano

 

hdu 6266 <http://acm.hdu.edu.cn/showproblem.php?pid=6266>


题意:有T组数据,每组数据输入一个n,d,n为石子堆的数目,d为1表示Hakase先取,2表示Nano先取,然后输入n个数据表示第i堆石子有ai个石子,一次只能去一堆任意个石子切最少取一个,Hakase每次必须取两次,Nano每次必须取一次。Hakase赢就输出Yes否则输出No。


思路:不难发现d=1时,当且仅当石子堆数是3的倍数且每堆石子的数量只能是1,Hakase才能输,d=2时只要Nano可以构造d=1的情况Hakase才能输。比如说1
1 x(x>1)或者1 1 1 x(x为任意数)就可以构造1 1 1使Hakase输。
#include<stdio.h> int main() { int T; scanf("%d",&T); while(T--) { int
i,n,k,t; int sum=0; scanf("%d%d",&n,&k); if(k==1) { for(i=1;i<=n;i++) {
scanf("%d",&t); if(t==1) sum++; } if(sum==n&&sum%3==0) printf("No\n"); else
printf("Yes\n"); } else { for(i=1;i<=n;i++) { scanf("%d",&t); if(t==1) sum++; }
if((sum==n&&n%3==1)||(sum+1==n&&n%3==1)||(sum+1==n&&n%3==0)) printf("No\n");
else printf("Yes\n"); } } }
 

J题  Master of GCD

 

hdu 6273 <http://acm.hdu.edu.cn/showproblem.php?pid=6273>


题意:题意很简单就是求整个数列的最大公约数,有T组数据,模数是998244353,有一个长度为n的数列,数列每项初始值为1,m个操作,每次操作有一个给定区间,以及操作方法,x为2就是给定区间每个数乘以2,为3就是给定区间每个数乘以3,操作完就求整个数列的最大公因数。


方法:很明显线段树的题,每个节点保存的信息有2的个数和3的个数,最后统计第一个节点共有几个2和几个3,然后再去相乘就行,但是这是区间更新,比较麻烦,所以每个节点要保存两组数据,一组是自己这个节点的区间更新了几个2和几个3,另一组是min(两个儿子节点的区间2的个数和3的个数),那么一个节点所在区间总共的2的个数和3的个数就是这两组数据相加。
#include<stdio.h> #include<string.h> #define max(x,y) x>y?x:y #define min(x,y)
x<y?x:y const int mod=998244353; struct node { int
two[2];//two[0]为该区间跟新次数,two[1]为左儿子总共的2的个数和右儿子总共2的个数的min int three[2];
}tree[300000]; void update(int L,int R,int ql,int qr,int node,int k) {
if(L>=ql&&R<=qr) { if(k==2) tree[node].two[0]++; else tree[node].three[0]++;
return; } int m=(L+R)/2; if(ql<=m) update(L,m,ql,qr,node*2,k); if(qr>m)
update(m+1,R,ql,qr,node*2+1,k); int
sumL=tree[node*2].two[0]+tree[node*2].two[1]; int
sumR=tree[node*2+1].two[0]+tree[node*2+1].two[1];
tree[node].two[1]=min(sumL,sumR);
sumL=tree[node*2].three[0]+tree[node*2].three[1];
sumR=tree[node*2+1].three[0]+tree[node*2+1].three[1];
tree[node].three[1]=min(sumL,sumR); } int main() { int T; scanf("%d",&T);
while(T--) { int i,n,q,l,r,k; scanf("%d%d",&n,&q); for(i=1;i<=2*n+1;i++) {
tree[i].three[0]=tree[i].two[0]=0; tree[i].three[1]=tree[i].two[1]=0; }
while(q--) { scanf("%d%d%d",&l,&r,&k); if(l>r) update(1,n,r,l,1,k); else
update(1,n,l,r,1,k); } long long ans=1; k=tree[1].two[0]+tree[1].two[1];
while(k) { ans=ans*2%mod; k--; } k=tree[1].three[0]+tree[1].three[1]; while(k)
{ ans=ans*3%mod; k--; } printf("%lld\n",ans%mod); } }

友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信