9.19[XJOI] NOIP训练37

时间：2021-03-05 09:13:57

上午[XJOI] NOIP训练37

T1 同余方程

Problem description

已知一个整数a,素数p,求解 $x^{2}\equiv a(mod p) $ 是否有整数解

Solution

据说是二次剩余

作为一个蒟蒻,非常不正经的来证一下

由于p是质数,所以

(1) 当p=2,则一定有解

(2) 如果p<>2

\(x\equiv a^{\frac{1}{2}}(mod p)\)

\(x^{p-1}\equiv a^{\frac{p-1}{a}}(modp)\)

又因为费马小定理

\(x^{p-1}\equiv 1(modp)\)

所以\(a^{\frac{p-1}{2}}\equiv 1(modp)\),

这样就很完美的得到了答案

Code

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll T,a,p,ans;

ll pow(ll a,ll b){

    ll res=1,base=(b-1)/2;

    if (a==0) return 0;

    while(base){

        if (base&1) res=res*a%b;

        base>>=1; a=a*a%b;

    }

    return res;

}

int main(){

    scanf("%d",&T);

    while (T--){

        scanf("%lld%lld",&a,&p);

        ans=pow(a,p);

        if (ans==1) printf("YES\n");

            else printf("NO\n");

    }

}

T2 重复串

Problem description

求最少删掉几个字符,使得最后答案成为重复串

Solution

这可能是我做过最简单的T2吧,

最暴力的O(\(n^{3}\))Dp,枚举中点,然后做一个lcs

T3 摘苹果

Solution

直接进行树上贪心,对于每个节点，将它的每个子节点当做一个叶子结点(及合并了子树的信息),

然后找出最大的l，然后判断哪些子节点的r小于这个l，那么这说明只能独立减掉。

其他的节点则可以合并到根节点上，变成一个节点，只是lr变了一下而已。

(此段文字为whc大佬所言) 在此%%%whc

Code

#include<bits/stdc++.h>

using namespace std;

int l,r,ans=0;

void dfs(int &l,int &r){

	int k,x,y;

	l=0; scanf("%d",&k);

	if (k==0) scanf("%d%d",&l,&r);

	else {

		vector <int> a;

		for (int i=0;i<k;++i)

			dfs(x,y),l=max(l,x),a.push_back(y);

		sort(a.begin(),a.end());

		for (int i=0;i<k;++i)

			if (a[i]<l) ++ans;

			else{

				r=a[i]; return;

			}

	}

}

int main(){

	dfs(l,r);

	printf("%d",ans+1);

	return 0;

}

下午及晚上

非常快的迅速订完题目,然后的然后,我也不知道了

一日总结

今天破天荒的用了一下markdown来写博客

对于这个不能调字体我也是非常无奈啊

决定如果没有数学题,绝不用markdown

还有这里我要严重吐槽一下各科老师,对!所有老师!

一次又一次的加深了我对xj的**感情

当然我会努力只在这里呆一年的,但对于在这儿的每一天,我一定都会过好

相关文章