题目链接:http://codeforces.com/contest/1139/problem/D
题目大意
给定一个流程：初始为一个数m，
每次等概率的添加一个1到m范围的数，
直到其共同的gcd为1，流程结束，计算期望长度。
题目分析
我们不妨分析这个串最后结束前,其gcd是多少,假设p是他们共同的gcd,
那么对于1到m这个整理,有多少个数是p的倍数?答案是,那么就有个
数不是p的倍数,那么对于下一个出现的数只要出现在不是p倍数的集合中就可以结束该串,
并且我们可以知道概率.
所以对于特定的p,我们定义表示其最后的gcd是p的串的期望长度,
但是对于所有的p其是有重复计算的,比如2和3算完了可能就把6算进去了,用莫比乌斯函数容斥下即可,最后求和计数.
注意点是答案初始值为1,然后p从2开始扫描,代码不难
答案初始值是1是因为对于m=1的情况其答案为1,我们讨论p的同时其实改变了m.(口胡....T_T)
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=1e5+5;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：
给定一个流程：初始为一个数m，
每次等概率的添加一个1到m范围的数，
直到其共同的gcd为1，流程结束，计算期望长度。题目分析：*/
int m,prim[maxn],tot=0;
int vis[maxn],miu[maxn];
void sieve(){miu[1]=1;for(int i=2;i<=m;i++){if(vis[i]==0) prim[tot++]=i,miu[i]=1;for(int j=0;j<tot;j++){if(i*prim[j]>m) break;int tp=i*prim[j];vis[tp]=1;if(i%prim[j]) miu[tp]=-miu[i];else break;}}
}
int main(){cin>>m;sieve();ll ans=1;rep(i,2,m+1) if(miu[i]){ans=(ans+miu[i]*(m/i)*powmod(m-m/i,mod-2)+mod)%mod;}cout<<ans<<endl;return 0;
}