发布时间: 2017年7月9日 18:17 最后更新: 2017年7月9日 21:05 时间限制: 1000ms 内存限制: 128M
描述欧拉函数 ϕ(n) 被定义 1 ~ n 中与 n 互质的数的个数。例如 ϕ(5)=4 ，因为 1 , 2 , 3 , 4 这四个数字与 5 互质。
定义 f 函数:
f(n)=∑i=233n−233ϕ(i)∗[n/i]
其中 [n/i] 表示 n 除以 i 所得到的商
输入第一行一个整数 T ，表示测试组数。对于每组数据，输入一行，包含一个数字 n ， 466<=n<=108
输出每组数据输出一行，表示函数值 f(n) 对 1000000007 取模
样例输入1 2 1068 972 样例输出1 293824 222698 #include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; const int TOP = 1e8 + 10; bool notprime[TOP]; int p[TOP / 5], pnum; int euler[TOP]; //在O(n)时间复杂度内求得TOP范围内所有数的欧拉函数 void Euler_All() { euler[1] = 1; for (int i = 2; i < TOP; ++i) { if (!notprime[i]) { p[++pnum] = i; euler[i] = i - 1; } for (int j = 1; j <= pnum && p[j] * i < TOP; ++j) { notprime[p[j] * i] = 1; if (i % p[j] == 0) { euler[p[j] * i] = euler[i] * p[j]; break; } else euler[p[j] * i] = euler[i] * (p[j] - 1); } } for (int i = 1; i < TOP; ++i) { gadd(euler[i], euler[i - 1]); } } int Euler_Single(int n) { int ans = n; for (int i = 2; i * i <= n; ++i)if (n % i == 0) { ans = ans - ans / i; while (n%i == 0)n /= i; } if (n > 1)ans = ans - ans / n; return ans; } int n; int main() { /* Euler_All(); */ scanf("%d", &casenum); for (casei = 1; casei <= casenum; ++casei) { scanf("%d", &n); int ans = (LL)n * (n + 1) / 2 % Z; for (int i = 1; i < 233; ++i) { gadd(ans, Z - Euler_Single(i) * (n / i) % Z); } for (int i = n - 232; i <= n; ++i) { gadd(ans, Z - Euler_Single(i) * (n / i) % Z); } /* for (int l = 233, r; l <= n - 233; l = r + 1) { //[l, r]范围的数，都是*[n / l] r = n / (n / l); gmin(r, n - 233); gadd(ans, (LL)(Z + euler[r] - euler[l - 1]) * (n / l) % Z); } */ printf("%d\n", ans); } return 0; } /* 【Trick && 吐槽】 一开始看不到给了多少空间 于是本来想的是预处理 + 下底函数分块 然而空间不够啦！ 【题意】 http://acmoj.shu.edu.cn/problem/418/ 【分析】 因为有性质—— 一个数的所有约数（包括自己）的欧拉函数之和，等于这个数本身的值 所以， ∑euler[i] * n / i 其实就是反着来考虑上面的性质，我们先考虑枚举每个数，考虑这个数作为约数的情况。 发现，对i的所有倍数，它作为约数时，都贡献了一个euler[i]， 即euler[i]贡献了n / i次，于是，如果这个式子的积累区间是[1, n]，结果就是n(n+1)/2 这道题我们只需要对前232和后233个数特殊处理去除就好啦！ 去除可以是233*sqrt()求欧拉函数，也可以是用区间筛法—— for(int i=1;i<=N;i++)phi[i]=i; for(int i=2;i<=N;i++)if(i==phi[i])//是素数 { for(int j=i;j<=N;j+=i) { phi[j]=phi[j]/i*(i-1); } } 【时间复杂度&&优化】 O(233 * sqrt(1e8)) 优化之后 O(233 * log级别) */
