生活随笔
收集整理的这篇文章主要介绍了
筛法 V - 一道水题
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
一天，szb 在上学的路上遇到了灰太狼。
灰太狼：帮我们做出这道题就放了你。
szb：什么题？
灰太狼：求一个能被 [1,n] 内所有数整除的最小数字，并对 100000007 取模。
szb：这题太水了，就让我小弟来做好了。
然后你就光荣的接受了这个任务。
Input
一行一个数 n。
Output
一行一个数 ans。
Example
样例输入
10
样例输出
2520
Hint
n≤108
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<cstdio>
#include<vector>
#include<set>
#include<cstring>
#include<cstdlib>
#include<time.h>
#include<stack>
#define INF 0x3f3f3f3f
using namespace std
;
const int maxn
=100;
typedef long long ll
;
ll mod
=1e8+7;
ll num
,f
[maxn
];
struct mat
{ll m
[maxn
][maxn
];
}ans
,a
;
ll
mode(ll a
,ll b
){ll sum
=1;a
=a
%mod
;while(b
){if(b
&1)sum
=(sum
*a
)%mod
;b
/=2;a
=(a
*a
)%mod
;}return sum
;
}
ll
inv(ll a
,ll b
){return(a
*mode(b
,mod
-2))%mod
;
}
ll
gcd(ll a
, ll b
) {return b
?gcd(b
, a
%b
):a
;
}
ll
lcm(ll x
, ll y
){return x
/ gcd(x
, y
)*y
;
}
ll
exgcd(ll a
,ll b
,ll
&x
,ll
&y
){if(b
==0){x
=1;y
=0;return a
;}int r
=exgcd(b
,a
%b
,x
,y
);int temp
=y
;y
=x
-(a
/b
)*y
;x
=temp
;return r
;
}
mat
mul(mat a
,mat b
,int n
){mat c
;memset(c
.m
,0,sizeof(c
.m
));for(int i
=1;i
<=n
;i
++)for(int j
=1;j
<=n
;j
++)for(int k
=1;k
<=n
;k
++)c
.m
[i
][j
]=(c
.m
[i
][j
]+(a
.m
[i
][k
]*b
.m
[k
][j
])%mod
)%mod
;return c
;
}
mat
_power(mat a
,int b
,int n
){memset(ans
.m
,0,sizeof(ans
.m
));for(int i
=1;i
<=n
;i
++)ans
.m
[i
][i
]=1;while(b
){if(b
&1)ans
=mul(a
,ans
,n
);a
=mul(a
,a
,n
);b
>>=1;}return ans
;
}void init(int n
){int vis
[maxn
];for(int i
=2;i
<=n
;i
++){if(vis
[i
])continue;for(int j
=i
*2;j
<=n
;j
+=i
)vis
[j
]=1;}
}
int oula(int x
)
{int i
,j
;int num
= x
;for(i
= 2; i
*i
<= x
; i
++){if(x
% i
== 0){num
= (num
/i
)*(i
-1);while(x
% i
== 0){x
= x
/ i
;}}}if(x
!= 1) num
= (num
/x
)*(x
-1);return num
;
}
const int mx
=1e8+5;
bool vis
[mx
];
int z
[1000000];
int main()
{int n
,cnt
=0;scanf("%d",&n
);ll ans
=1;memset(vis
,0,sizeof(vis
));for(int i
=2;i
<=n
;i
++){if(!vis
[i
]){z
[cnt
++]=i
;for(ll j
=i
;j
<=n
;j
*=i
)ans
=ans
*i
%mod
;}for(int j
=0;j
<cnt
;j
++){ll v
=i
*z
[j
];if(v
>n
)break;vis
[v
]=1;if(i
%z
[j
]==0)break;}}printf("%lld\n",ans
);return 0;
}
总结
以上是生活随笔为你收集整理的筛法 V - 一道水题的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
