Finding the Order
链接:https://ac.nowcoder.com/acm/contest/5669/F
思路比较简单,有关图形的题目还是要多动手。
• 找到这四个距离的最大值。
• 如果最大值来自 AD 或 BC,则 AB//CD,否则 AB//DC。
#include<iostream> using namespace std; int main(){ int T; scanf("%d",&T); while(T--){ int a, b, c, d; scanf("%d%d%d%d",&a,&b,&c,&d); puts(max(b,c)>=max(a,d)?"AB//CD":"AB//DC"); } }
Basic Gcd Problem
链接:https://ac.nowcoder.com/acm/contest/5669/B
这类题目应该先在纸上推一推,找一找规律或者转换一下题目的形式。这道题目如果能够发现
f(x)=c^(x的质因子个数),剩下的内容就比较容易了
#include<cstdio> #define ll long long using namespace std; const int mod=1e9+7; int main(){ int t,c,n; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&c); ll ans=1; for(int i=2;i*i<=n;i++) while(n%i==0){ n/=i; ans=ans*c%mod; } if(n>1) ans=ans*c%mod; printf("%lld\n",ans); } return 0; }
Harder Gcd Problem
链接:https://ac.nowcoder.com/acm/contest/5669/H
看了一下CSDN上的题解,这道题的解法还是非常多的。不过个人觉得还是贪心的思路更为简洁简单。
思路:因为一个素数越大,与他匹配的数就会越少,所以考虑优先匹配较大的素数。
这样保证每个含因子是该素数的尽可能被匹配到,因为是一组是两个数,所以当满足条件的数的为奇数个时,显然我们要扔掉一个看是否能和其他数匹配,显然能与最小的质数2匹配的数是最多的,所以我们保留一下是2的倍数的数,如果已经匹配了奇数个,就直接把它给该素数作为贡献,否则给2的倍数进行匹配。
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=2e5+5; int p[N],n,t,cnt,ans[N],tot; bool a[N],vis[N]; void pre(){ int n=2e5; for(int i=2;i<=n;i++){ if(!a[i]) p[cnt++]=i; for(int j=0;j<cnt&&i*p[j]<=n;j++){ a[i*p[j]]=true; if(i%p[j]==0) break; } } } int main(){ pre(); scanf("%d",&t); while(t--){ scanf("%d",&n);tot=0; for(int i=1;i<=n;i++) vis[i]=0; int pos=upper_bound(p,p+cnt,n/2)-p-1; for(int i=pos;i;i--){ for(int j=p[i];j<=n;j+=p[i]){ if(vis[j]||j==(p[i]<<1)) continue; ans[++tot]=j,vis[j]=1; } if(tot&1) vis[(p[i]<<1)]=1,ans[++tot]=(p[i]<<1); } printf("%d\n",tot>>1); for(int i=1;i<=tot;i+=2) printf("%d %d\n",ans[i],ans[i+1]); } return 0; }