CH Round #55 - Streaming #6 (NOIP模拟赛day2) - Linux

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

A.九九归一

题目：http://ch.ezoj.tk/contest/CH%20Round%20%2355%20-%20Streaming%20%236%20(NOIP模拟赛day2)/九九归一

题解：题目意思就是问 a是不是n的一个原根

首先如果 gcd(a,n)!=1 显然不可能输出0

然后我们有性质

若 gcd(a,n)==1 则 a模n的阶k|phi（n）

所以就可以枚举phi(n)的约数判定了

复杂度题解中说是 q*logn*logn*logn的。。。

代码：

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 100000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,tot,a[maxn];
int power(int xx,int yy)
{
ll t=,x=xx,y=yy;
for(;y;y>>=,x=(x*x)%n)
if(y&)t=(t*x)%n;
return t;
}
inline bool check(int m)
{
for1(i,tot)if(power(m,a[i])==)return ;
return ;
}
inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();
int x=n,y=n;
for2(i,,sqrt(n))
if(x%i==)
{
y=(y/i)*(i-);
while(x%i==)x/=i;
}
if(x!=)y=(y/x)*(x-);
for1(i,y)if(y%i==)a[++tot]=i;tot--;
int cs=read();
while(cs--)
{
int m=read();
if(gcd(m,n)!=)printf("");
else if(check(m))printf("");
else printf("");
}
printf("\n");
return ;
}

B.LCA的统计

题目：http://ch.ezoj.tk/contest/CH%20Round%20%2355%20-%20Streaming%20%236%20(NOIP模拟赛day2)/LCA的统计

题解：首先枚举是一定要的，我们枚举 lca(i,j)然后看一下什么样的i，j是我们枚举的这个值。

稍微想想会发现f[x]=w[x]*（(s[x]*s[x])-sigma（s[y]*s[y]）） y是x 的子树

然后防止爆long long 就行了

代码：

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 1500000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
struct edga{int go,next;}e[maxn];
int n,tot,head[maxn];
ll s[maxn],f[maxn],w[maxn];
inline void insert(int x,int y)
{
e[++tot].go=y;e[tot].next=head[x];head[x]=tot;
}
void dfs(int x)
{
f[x]=;s[x]=w[x];
for(int i=head[x],y;i;i=e[i].next)
{
dfs(y=e[i].go);
f[x]=((f[x]-w[x]*(s[y]*s[y]%mod))%mod+mod)%mod;
s[x]=(s[x]+s[y])%mod;
}
f[x]=(f[x]+w[x]*(s[x]*s[x]%mod))%mod;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();w[]=read()%mod;
for2(i,,n)insert(read(),i),w[i]=read()%mod;
dfs();
ll ans=;
for1(i,n)ans=(ans+f[i])%mod;
printf("%lld\n",ans);
return ;
}

C.四驱兄弟

题目：http://ch.ezoj.tk/contest/CH%20Round%20%2355%20-%20Streaming%20%236%20(NOIP模拟赛day2)/四驱兄弟

题解：猜想大概是MST，然后发现不会证，就打了弃疗了。结果A了。。。

出题人是这样说的：

考虑图连通的情况，那么假设最小生成树不是第k小边最小生成树，就可以把两个树各取一点变成一个更小的生成树，就矛盾了

没想到我用map+cin居然没T

代码：

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1100000000
#define maxn 200000+1000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
typedef map<string,int>::const_iterator cit;
typedef map<string,int>::value_type vt;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
map<string,int>mp;
struct rec{int u,v,w;}e[maxn];
int n,m,tot,a[maxn],fa[maxn];
string s;
inline bool cmp(rec a,rec b)
{
return a.w<b.w;
}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();m=read();
for1(i,m)
{
e[i].w=read();
cin>>s;
cit j=mp.find(s);
if(j!=mp.end())e[i].u=j->second;
else
{
mp.insert(mp.begin(),vt(s,++tot));
e[i].u=tot;
}
cin>>s;
j=mp.find(s);
if(j!=mp.end())e[i].v=j->second;
else
{
mp.insert(mp.begin(),vt(s,++tot));
e[i].v=tot;
}
}
sort(e+,e+m+,cmp);
for1(i,tot)fa[i]=i;
int j=;
for1(i,n)
{
while(j<=m&&find(e[j].u)==find(e[j].v))j++;
if(j>m)a[i]=inf;
else
{
a[i]=e[j].w;
fa[find(e[j].u)]=find(e[j].v);
}
j++;
}
for1(i,n)
if(a[i]==inf)printf("INF\n");else printf("%d\n",a[i]);
return ;
}