Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2019
718
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.50 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. #define mod 1000000007
  4. long long pow_log(long long x,int y)
  5. {
  6.     if (!y)
  7.     return 1;
  8.     long long ret=pow_log(x,y/2);
  9.     ret=(ret*ret)%mod;
  10.     if (y%2)
  11.     ret=(ret*x)%mod;
  12.     return ret;
  13. }
  14. int ans[100005];
  15. int main()
  16. {
  17.     int m,res=1;
  18.     scanf("%d",&m);
  19.     for (int i=m;i>1;i--)
  20.     {
  21.         ans[i]=(pow_log(mod+1-((m/i*pow_log(m,mod-2))%mod),mod-2)-1+mod)%mod;
  22.         for (int j=2*i;j<=m;j+=i)
  23.         ans[i]=(ans[i]-ans[j]+mod)%mod;
  24.         res=(res+ans[i])%mod;
  25.     }
  26.     printf("%d",res);
  27. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement