Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- #define mod 1000000007
- long long pow_log(long long x,int y)
- {
- if (!y)
- return 1;
- long long ret=pow_log(x,y/2);
- ret=(ret*ret)%mod;
- if (y%2)
- ret=(ret*x)%mod;
- return ret;
- }
- int ans[100005];
- int main()
- {
- int m,res=1;
- scanf("%d",&m);
- for (int i=m;i>1;i--)
- {
- ans[i]=(pow_log(mod+1-((m/i*pow_log(m,mod-2))%mod),mod-2)-1+mod)%mod;
- for (int j=2*i;j<=m;j+=i)
- ans[i]=(ans[i]-ans[j]+mod)%mod;
- res=(res+ans[i])%mod;
- }
- printf("%d",res);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement