51nod 1225 나머지 수의 합 수론
제목 연결:
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1225
Description
F(n) = (n % 1) + (n % 2) + (n % 3) + ...... (n % n)。그 중% 는 모드, 즉 나머지 라 고 답 했다.예 를 들 어 F (6) = 6% 1 + 6% 2 + 6% 3 + 6% 4 + 6% 5 + 6% 6 = 0 + 0 + 0 + 2 + 1 + 0 = 3.n 을 주 고 F (n) 를 계산 합 니 다. 결과 가 매우 크기 때문에 Mod 1000000007 의 결 과 를 출력 하면 됩 니 다.
Input
숫자 N (2 < = N < = 10 ^ 12) 을 입력 하 십시오.
Output
출력 F (n) Mod 1000000007 결과
Sample Input
6
Sample Output
3
Hint
제목
문제 풀이:
나머지 = n - n / i * i
n / i 는 n 의 인자 개수 만 있 는 것 이 분명 하 다.
그리고 n / i 는 연속 적 인 구간 내 에서 모두 같다.
이것 은 등차 서열 로 i 를 유지 하면 됩 니 다.
그리고 sqrtn 의 복잡 도 에서 이 문 제 를 해결 할 수 있 습 니 다.
코드
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
long long quickpow(long long m,long long n,long long k)// m^n%k
{
long long b = 1;
while (n > 0)
{
if (n & 1)
b = (b*m)%k;
n = n >> 1 ;
m = (m*m)%k;
}
return b;
}
long long mul(long long a,long long b)
{
if(a>=mod)a%=mod;
if(b>=mod)b%=mod;
a=a*b;
if(a>=mod)a%=mod;
return a;
}
int main()
{
long long n;
cin>>n;
long long ans=0;
for(int i=1;i<=sqrt(n);i++)
{
if(n/i==i)
{
long long temp=n/i*i;
ans=(ans+n-temp+mod)%mod;
continue;
}
long long r=n/i;
long long l=n/(i+1)+1;
long long num=mul(mul(mul((r+l),quickpow(2,mod-2,mod)),(r-l+1)),i);
//cout<<mul(n,r-l+1)<<" "<<num<<" "<<i<<" "<<r<<" "<<l<<endl;
ans=(ans+mul(n,r-l+1)-num+mod)%mod;
ans=(ans+n-mul(n/(n/i),(n/i))+mod)%mod;
}
cout<<ans<<endl;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
