ACM训练半周日记—11月9日

时间:2022-07-04 13:51:34

         这个半周在做题,收获了一些知识点和智商。整理下吧。

        I题:给出两个数n,m,求m是否能被n!整除。

        笔记:设f(n,p)表示n!得质因数里有f(n,p)个p,那么f(n,p)=f(n/p,p)+n/p;(p是质数)(当n<p是f=0)

inline int idx(int n, int p)//在O(log n / log p)时间内求出n!的质因子分解中质数p的指数
{

        int sum = 0;
while (n)
{
n /= p;
sum += n;
}
return sum;
}

         这样I题就可以先分解m成素数,然后看m的素因子数是否多于被n!的指数。

         R题:求n以内两两互质的数(2,3)和(3,2)是两对,注意(1,1)这个情况。

        那么求出n以内的欧拉函数,加和乘2-1,可以了。

         K就是求裸的欧拉函数,注意欧拉函数只是求>=2的情况,当n==1时,输出0(很显然,欧拉函数1时是1,要改为0)。

        H题就是求n!可以被分解为多少个素数。这题出乎意料的是暴力法,求1到1000000(数据范围)内所有数可被分为多少素数,然后加和。注意,1000000内的数最多有一个1000以上的素数(显然)。

         B题:给两个杯子分别容量n,m,求fill,pour,empty这些操作使m杯子里有n量水。这题是特判,只要符合要求就行,所以就是不断向a倒满,a倒入b(a<b,n<b),当b满了就全倒掉,不断重复,一定卡得到答案。注意:叫了好几次去不tle,注意细节,当a=n,b=n,a=1,时直接处理可以节省时间。