Rng(求逆元)-白红宇

Rng(求逆元)

阅读量：5010 次

发布时间：2019-06-12

本文共 1313 字，大约阅读时间需要 4 分钟。

Problem Description

Avin is studying how to synthesize data. Given an integer n, he constructs an interval using the following method: he first generates a integer r between 1 and n (both inclusive) uniform-randomly, and then generates another integer l between 1 and r (both inclusive) uniform-randomly. The interval [l, r] is then constructed. Avin has constructed two intervals using the method above. He asks you what the probability that two intervals intersect is. You should print p*

求逆元的几种方法:

Input

Just one line contains the number n (1 ≤ n ≤ 1, 000, 000).

Output

Print the answer.

Sample Input

Sample Output

750000006

规律：(n+1)*n/2/(n*n)

代码：

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 const int maxn=1e5+5;const long long mod=1e9+7; typedef long long ll;using namespace std;ll ksm(ll x,ll y){ ll ans=1; while(y) { if(y&1) ans=ans*x%mod; y>>=1; x=x*x%mod; } return ans;} int main(){ ll n; while(cin>>n) { ll p=(n+1)*n/2; ll q=n*n; printf("%lld\n",(p*ksm(q,mod-2))%mod); } return 0;}

转载于:https://www.cnblogs.com/Staceyacm/p/11221390.html

你可能感兴趣的文章