单测试点时限: 1.0 秒
内存限制: 512 MB
Mo偶然间得到一个数学问题，听说你很擅长数学，于是前来虚心请教！
求区间 $[1,n]$ 中 与 $m$ 互质的数的乘积。
输入
多组输入（不超过$100$组）
每行两个整数 $n$ 和 $m$. $( 0<n≤10^6, 0<m≤10^9)$
输出
每行输出一个答案.(由于答案很大，故请输出对 $10^9+7$ 取模后的结果)
样例
input
output
Solve
正解是容斥，但是没有推出来公式，就暴力写了，结果还过了2333333（虽然每个点的时间都在$300$ms以上）
暴力的写法：
对$m$进行质因数分解，在区间$[1,n]$中，对$m$的质因数的倍数进行标记（包括质因数），然后遍历区间$[1,n]$，将未标记过的数乘起来
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<bits/stdc++.h>
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
const int maxn=1e6+10;
const int maxm=1e3+10;
const int inf=(1<<30);
const ll INF=(1LL*1<<60);
const int mod=1e9+7;
using namespace std;
int arr[maxn];
int p;
int pr[maxn];
int mp[maxn];
void getp(int n)
{
p=0;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
arr[p++]=i;
while(n%i==0)
n/=i;
}
}
if(n>1)
arr[p++]=n;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
int n,m;
while(cin>>n>>m)
{
ms(mp,0);
int cnt=0;
getp(m);
for(int i=0;i<p;i++)
{
for(int j=1;j*arr[i]<=n;j++)
{
mp[arr[i]*j]++;
}
}
ll ans=1;
for(int i=1;i<=n;i++)
{
if(!mp[i])
ans=1LL*(ans%mod*1LL*i%mod)%mod;
}
cout<<ans<<endl;
}
return 0;
}
|