XXY 的 的 NOIP 模擬賽 4 4 —— 數(shù)學(xué)專場(chǎng)

A

Description
定義 f（x）表示 x 的約數(shù)和，例：f（12）=1+2+3+4+6+12=28
給出 x，y，求Σf（i），i∈[x,y]
Input
一行兩個(gè)整數(shù) x，y
Output
一行表示答案
Example
兩組輸入數(shù)據(jù)
2 4
123 321
對(duì)應(yīng)輸出
14
72543
Hint
對(duì)于 20%的數(shù)據(jù)，1<=x<=y<=1000
對(duì)于 40%的數(shù)據(jù)，1<=x<=y<=1e7
對(duì)于 100%的數(shù)據(jù)，1<=x<=y<=2e9

#include<iostream> #include<cstdio> using namespace std; long long x,y; long long count(int x){long long res=0;long long l=1,r;while(1){r=x/(x/l);long long a=x/l;res+=((l+r)*(r-l+1)/2)*a;l=r+1;if(x/l==0)break;}return res; } int main(){freopen("A.in","r",stdin);freopen("A.out","w",stdout);cin>>x>>y;long long ansl=count(x-1);long long ansr=count(y);cout<<ansr-ansl; } 90分 出現(xiàn)整數(shù)被0除的錯(cuò)誤 #include<iostream> #include<cstdio> using namespace std; long long x,y; long long count(int x){long long res=0;long long l=1,r;while(1){if(x/l==0)r=x;else r=x/(x/l);long long a=x/l;res+=((l+r)*(r-l+1)/2)*a;l=r+1;if(x/l==0)break;}return res; } int main(){freopen("A.in","r",stdin);freopen("A.out","w",stdout);cin>>x>>y;long long ansl=count(x-1);long long ansr=count(y);cout<<ansr-ansl; } 100分

?

B

Description
求滿足以下條件的 x 的個(gè)數(shù)
① x∈[1,n!]
② 設(shè) pi 為質(zhì)數(shù)且 pi|x，那么 pi>m，對(duì)于所有的 pi 均成立
答案對(duì) 100000007 取模
Input
一行兩個(gè)整數(shù) n，m
Output
一行表示答案
Example
3 組輸入樣例
100 10
100 20
10000 9000
Output
對(duì)應(yīng) 3 組輸出
43274465
70342844
39714141
Hint
對(duì)于 20%的數(shù)據(jù)，n，m<=8
對(duì)于 60%的數(shù)據(jù)，n<=100000,m<=8
對(duì)于 100%的數(shù)據(jù)，n<=10000000，保證 n-m<=100000，m<=n

學(xué)到的一點(diǎn)東西

1.x的所有素因子大于m，則x與m!互素
2.已知phi[(i-1)!],遞推地求phi[i!]
　　如果i是素?cái)?shù),phi[i!]=phi[(i-1)!]*(i-1)
　　如果i不是素?cái)?shù)，phi[i!]=phi[(i-1)!]*i

3.phi[n!]=phi[m!]*(n!/m!)

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int p[10000],n,m,w=1,ans,cnt; bool vis[10000000],q[1000000]; void dfs(int pos,long long sum){if(sum>w)return;if(!q[sum]&&sum!=1)ans++,q[sum]=1;//cout<<sum<<' ';for(int i=pos;i<=cnt;i++){if(sum*p[i]>w)return;dfs(i,sum*p[i]);} } int main(){//freopen("Cola.txt","r",stdin);freopen("B.in","r",stdin);freopen("B.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)w*=i;for(int i=2;i<=w;i++){if(!vis[i])p[++cnt]=i;for(int j=1;j<=cnt&&i*p[j]<=w;j++){vis[i*p[j]]=1;if(i%p[j]==0)break;}}int pos=upper_bound(p+1,p+cnt+1,m)-p;dfs(pos,1);for(int i=pos;i<=cnt;i++){if(cnt>w)break;if(!q[p[i]])ans++;}cout<<ans; } 20分 暴力 #include<cstdio> #define N 10000001 #define mod 100000007 using namespace std; int cnt,p[664580],phi[N]; long long phifac[N]; bool v[N]; int main() {freopen("B.in","r",stdin);freopen("B.out","w",stdout);phi[1]=1;for(int i=2;i<N;i++){if(!v[i]){p[++cnt]=i;phi[i]=i-1;}for(int j=1;j<=cnt;j++){if(i*p[j]>=N) break;v[i*p[j]]=true;if(i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-1);else{phi[i*p[j]]=phi[i]*p[j];break;}}}int n,m; long long ans;scanf("%d%d",&n,&m);ans=0;phifac[1]=1;for(int i=2;i<=m;i++) if(!v[i]) phifac[i]=phifac[i-1]*(i-1)%mod;else phifac[i]=phifac[i-1]*i%mod;ans=phifac[m];for(int i=m+1;i<=n;i++) ans=ans*i%mod;printf("%I64d\n",ans-1); } 100分

?

C

Description
令 f（k）=n 表示 有 n 種方式，可以把正整數(shù) k 表示成幾個(gè)素?cái)?shù)的乘積的形式。
例 10=2*5=5*2，所以 f（10）=2
給出 n，求最小的 k
Input
一行一個(gè)整數(shù) n
Output
一行表示答案
Example
四組輸入樣例
1
2
3
105
對(duì)應(yīng)輸出：
2
6
12
720
Hint
20%的數(shù)據(jù)，k<=20
另外 20%的數(shù)據(jù)，n<=20
另外 20%的數(shù)據(jù)，k<=1e6
100%的數(shù)據(jù)，k,n<=2^60

#include<iostream> #include<cstdio> using namespace std; long long a[50]; int k,n,bin[1000],p[100000],cnt; bool vis[1000000]; bool check(int x){int l=0,pos=1;while(x!=1){while(x%p[pos]!=0)pos++;l=l+1;bin[l]=0;while(x%p[pos]==0){bin[l]++;x=x/p[pos];}}long long res=1;int sum=0;for(int i=1;i<=l;i++)sum+=bin[i];res=a[sum];for(int i=1;i<=l;i++)res/=a[bin[i]];if(res==n)return 1;return 0; } int main(){//freopen("Cola.txt","r",stdin);freopen("C.in","r",stdin);freopen("C.out","w",stdout);a[1]=1;for(int i=2;i<=25;i++)a[i]=a[i-1]*i;scanf("%d",&n);for(int i=2;i<=100000;i++){if(!vis[i])p[++cnt]=i;for(int j=1;j<=cnt&&i*p[j]<=100000;j++){vis[i*p[j]]=1;if(i%p[j]==0)break;}}for(int i=2;i<=100000;i++){//k的所有可能值 if(check(i)){printf("%d",i);return 0;}} } 30分 暴力枚舉答案 #include<cstdio> #include<iostream> using namespace std; typedef long long LL; int p[21]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71}; LL ans,n; LL C[70][70]; void solve(int num,int lim,LL tot,LL now,int last) {if(now>ans) return;if(tot==n) { ans=now; return ; }if(tot>n || num>20) return;LL t=1;for(int i=1;i<=lim;i++){t*=p[num];if(now>=ans/t) return;solve(num+1,i,tot*C[last+i][i],now*t,last+i);} } int main() {freopen("C.in","r",stdin);freopen("C.out","w",stdout);C[0][0]=1;for(int i=1;i<70;i++){C[i][0]=1;for(int j=1;j<=i;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];} scanf("%I64d",&n);if(n==1){printf("1 2\n");return 0;}ans=(LL)1<<60;solve(1,63,1,1,0);printf("%I64d\n",ans); } 100分 搜索+剪枝

?

轉(zhuǎn)載于:https://www.cnblogs.com/thmyl/p/7574982.html

總結(jié)

以上是生活随笔為你收集整理的2017-9-22 NOIP模拟赛[xxy][数论]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。