18.12.1 Nuist_ACM集训队数论专场ABC题解

Problem A

题目：

HDU-4704

Sample Input

2

Sample Output

2

Hint

For N = 2, S(1) = S(2) = 1.The input file consists of multiple test cases. ==

这道题大致的意思就是给一个数N，问你将其分成1，2，3……N个数共有多少种分发。例如：4可以分成4；1，3；2，2；3，1；1，1，2；1，2，1；2，1，1；1，1，1，1；共8种分法。菜鸡没看懂题目，以为换了位置还算同一种。理解题意可知用排列组合的插空法计算并化简，即：S(0)+S(1)+S(2)+……+S(N)=CN0+CN1+……+CNNC_N^0+C_N^1+……+C_N^NCN0​+CN1​+……+CNN​=2N这个公式(实际是加到N-1，可是我打不出来上下两个N-1的标识，只能这样了)。那么现在的问题就是如何计算2的超大数次方取109+7的模。介于N的范围最大到10100000,long long肯定是存不下的，我的方法是用字符串一位一位取，下面给出大致解释：例如：2543=((25)10∗\ast∗ 24)10∗\ast∗ 23。所以对任意一个大数，用for循环就可以搞定，对于每次的10次方，快速幂即可。下面贴出代码：

#include <iostream>#include <cstdio>#include <cstring>#define mod 1000000007using namespace std;char a[1000005];//数字太大，当作字符串输进来 long long int len,biao[]={1,2,4,8,16,32,64,128,256,512},n,ans,i,t,flag=0;//只用2^0~2^9,直接打表了 int main(){while(gets(a)){len=strlen(a);a[len-1]-=1;//减1flag=0; for(i=len-1;i>=0;i--)//退位问题{a[i]=a[i]-flag;flag=0;if(a[i]<'0'){a[i]=a[i]+10; flag=1;}else break;}ans=1;for(i=0;i<len;i++)//算法实现过程 {n=9;t=ans;while(n)//快速幂 {if(n&1)ans=ans*t%mod;//每次取模 t=t*t%mod;n>>=1;}t=biao[a[i]-'0'];ans=ans*t%mod;}cout<<ans<<endl;//结果 }return 0;}

15ms通过，但看有0msAC的，上课还讲了其他的算法，但当时没听懂，到时候看看别人的题解再说

Problem B

题目：

HDU-1395

Give a numbern, find the minimumx(x>0) that satisfies 2^x mod n = 1

Input

One positive integer on each line, the value ofn.

Output

If the minimumxexists, print a line with 2^x mod n = 1.

Print 2^? mod n = 1 otherwise.

You should replacexandnwith specific numbers.

Sample input

2

5

Sample Output

2^? mod 2 = 1

2^4 mod 5 = 1

思路:这道题很明显能看出当n为偶数或1的时候是无解的，由欧拉定理可知奇数必有解菜鸡看不懂就只能直接上链接不详细解释（其实了解就好了）由于测试数据的设置，这题可以直接暴搜快速幂，但题目好坑，输出的句子中有几个空格，不认真看直接PE。下面直接贴代码:

#include <iostream>#include <cstdio>using namespace std;int main(){int n,i,x,t,j;while(cin>>n){if(n%2==0||n==1)//偶数和1显然去除 printf("2^? mod %d = 1\n",n);//格式，有有有空格 else{for(i=2;;i++) //暴搜 {x=i-1;j=2;t=2;while(x)//快速幂 {if(x&1)t=t*j%n;j=j*j%n;x>>=1; }if(t==1)break;}printf("2^%d mod %d = 1\n",i,n);//空格空格空格}} return 0;}

前面说到欧拉定理，其实这题可以它来对对暴搜的数据进行一次简化，来优化时间。由欧拉定理可知1~n-1中与n互质的数的个数m可使am≡\equiv≡ 1(mod n)，但m不一定是最小值，所以对m中所有不与m互质的数进行搜索，找到即可。（原理解释：设p*q==m，且am≡\equiv≡ 1(mod n)；则可能有ap≡\equiv≡ 1(mod n)且aq≡\equiv≡ 1(mod n)，所以只要找出m中所有不与m互质的数(即那些p和q)并对其进行搜索就好了，下面是优化后的代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define LL long long using namespace std;LL t,e[1000];LL mod;LL euler_phi(LL n)//欧拉函数，找到可能实现的最大值 {LL m=sqrt(n+0.5);LL ans=n,i;for(i=2;i<=m;i++) if(n%i==0) {ans=ans/i*(i-1);while(n%i==0)n=n/i;} if(n>1)ans=ans/n*(n-1);return ans;}void find(LL n)//找到与m不互质的数，这些是可能的解 {LL i;e[t++]=n;for(i=2;i*i<=n;i++) if(n%i==0)if(i*i==n)e[t++]=i; else {e[t++]=i;e[t++]=n/i; } }LL pows(LL a,LL b)//快速幂后取模 {LL s=1; while(b) {if(b&1) s=(s*a)%mod;a=(a*a)%mod;b>>=1; } return s;}int main(){LL n; while(cin>>n){if(n%2==0||n==1)printf("2^? mod %d = 1\n",n);else {LL m,ans,i,s=2; m=euler_phi(n);t=0; find(m);sort(e,e+t);//要从小到大有序地找最小 mod=n; for(i=0;i<t;i++) if(pows(2,e[i])==1){ans=e[i];break;} printf("2^%d mod %d = 1\n",ans,n); } } return 0;}

优化之后，耗时直接从405ms降到了31ms，效果还是很显著的。

总感觉上课还讲了其他的解法

Problem C

题目：

HDU-5750

A positive proper divisor is a positive divisor of a numbern, excludingnitself. For example,1,2, and3are positive proper divisors of6, but6itself is not.

Peter has two positive integersnandd. He would like to know the number of integers belownwhose maximum positive proper divisor isd.

Input

There are multiple test cases. The first line of input contains an integerT(1≤T≤106)(1≤T≤106), indicating the number of test cases. For each test case:

The first line contains two integersnandd(2≤n,d≤109)(2≤n,d≤109).

Output

For each test case, output an integer denoting the answer.

Sample Inout

9

10 2

10 3

10 4

10 5

10 6

10 7

10 8

10 9

100 13

Sample Output

1

2

1

0

0

0

0

0

4

这题的大致意思是要找到比n小且最大因数为d的数的个数，转换思想理解，就是当d为素数时，找比d小且乘d小于n的素数的个数；当d不为素数时，求乘d小于n且小于等于d的最小素因数的素数的个数（关于为什么小于等于最小素因数，例：n=17430，d=385，d=5∗\ast∗ 7∗\ast∗ 11,当选到7时，找到的数为5∗\ast∗ 7∗\ast∗ 7∗\ast∗ 11=2695，而2695的最大因数为539=7∗\ast∗ 7∗\ast∗ 11，此时不满足，结束）。那么，现在所要做的问题是：1.找出素数2.判断中止。为防止TLE，找素数可以(最好)用欧拉筛法(没找到百度百科的链接)来筛选素数(同时，因筛时只要找d的素因数，打表打到34000就差不多了），将埃氏筛的O(nlogn)的时间复杂度降到O(n)，具体实现在代码下说;中止判断条件由题意解析可知，以下为AC代码:

#include <iostream>#define MAXN 34000#define ll long long using namespace std;int num,prime[MAXN];bool vis[MAXN];void isprime()//欧拉筛法 {ll i,j;num=0;for(i=2;i<=MAXN;++i) {if(!vis[i])prime[num++]=i;for(j=0;j<=num&&i*prime[j]<=MAXN;++j){vis[i*prime[j]]=true;if(i%prime[j]==0)break;//欧拉筛法缩时关键 } }} int main(){int ans,i,N;ll n,d;isprime();//直接打表 std::ios::sync_with_stdio(false);//摆脱cin为保持与stdio同步而造成的TLE cin>>N;while(N--){cin>>n>>d;ans=0;for(i=0;i<num;++i){if(prime[i]>d||prime[i]*d>=n)//d为素数时的中止条件 break;if(d%prime[i]==0)//d为非素数时的中止条件 {++ans;break;}++ans;}cout<<ans<<endl;}return 0;}

悲惨地被c++的cin同步问题卡成TLE，加std::ios::sync_with_stdio(false);关闭同步或者直接用scanf和printf就好

1887ms过的，看着那些三位数的羡慕

关于欧拉筛的缩时问题，很多人会对if(i%prime[j]==0)break;这句话不理解，以下为解释：

欧拉筛法不是用i的倍数来消去合数，而是把prime里面纪录的素数，升序来当做要消去合数的最小素因子。当i是prime[j]的倍数时，i=k∗\ast∗prime[j]，如果继续运算 j+1，i∗\ast∗prime[j+1] = prime[j]∗\ast∗k∗\ast∗prime[j+1]，这里prime[j]是最小的素因子，当i = k∗\ast∗prime[j+1]时会重复筛一遍，所以才跳出循环。