uva 11440 - Help Tomisu(欧拉功能)

题目链接:uva 11440 - Help
Tomisu

题目大意:给定n和m,求从2~n。中的数x。要求x的质因子均大于m。问说x有多少个。答案模上1e9+7。

解题思路:

(1)n!=k∗m!(n≥m)

(2)
假设有gcd(x,T)=1,那么gcd(x+T,T)=gcd(x,T)=1

题目要求说x的质因子必需要大于m,也就是说x不能包括2~m的因子,那么gcd(x,m!)=1,于是我们求出ϕ(m!),小于m!

而且满足gcd(x,m!)=1的个数。

那么依据(2)可得从[m!+1, 2*m!]中的x个数也是ϕ(m!)个。由于假设存在gcd(x,T)=a,那么gcd(x+T,T)=gcd(x,T)=a.

又由于(1),所以最后n!以内的x个数为:n!∗ϕ(m!)m!

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std;
typedef long long ll;
const int maxn = 1e7;
const ll MOD = 100000007; int np, pri[maxn+5], vis[maxn+5];
ll fact[maxn+5], phi[maxn+5]; void prime_table (ll n) {
np = 0;
for (ll i = 2; i <= n; i++) {
if (vis[i])
continue; pri[np++] = i;
for (ll j = i * i; j <= n; j += i)
vis[j] = 1;
}
} void gcd (ll a, ll b, ll& d, ll& x, ll& y) {
if (b == 0) {
d = a;
x = 1;
y = 0;
} else {
gcd(b, a%b, d, y, x);
y -= (a/b) * x;
}
} inline ll inv_number (ll a, ll n) {
ll d, x, y;
gcd(a, n, d, x, y);
return (x + n) % n;
} void init (ll n) {
fact[1] = phi[1] = 1;
for (ll i = 2; i <= n; i++) {
fact[i] = (fact[i-1] * i) % MOD;
phi[i] = phi[i-1]; if (vis[i] == 0) {
phi[i] *= ((i-1) * inv_number(i, MOD)) % MOD;
phi[i] %= MOD;
}
}
} ll solve (int n, int m) {
ll ans = fact[n] * phi[m] % MOD;
return (ans - 1 + MOD) % MOD;
} int main () {
prime_table(maxn);
init (maxn); int n, m;
while (scanf("%d%d", &n, &m) == 2 && n + m) {
printf("%lld\n", solve(n, m));
}
return 0;
}

版权声明:本文博主原创文章。博客,未经同意不得转载。

上一篇:分布式服务跟踪及Spring Cloud的实现


下一篇:HBase 笔记2