HDU4407Sum (용 척 원리)
http://acm.hdu.edu.cn/showproblem.php?pid=4407
제목:
하나의 길이 가 n 인 서열, 시작 하 는 서열 은 1, 2, 3... n 이다.
그리고 또 두 가지 조작.
operation 1: 구간 [a, b] 에서 p 와 서로 질 적 인 수의 합 을 묻는다.
operation 2: 번호 가 i 인 수 를 x 로 변경 합 니 다.
조작 을 수정 하지 않 았 다 면, 분명 한 것 은 용 척 원리 이다.
계산 적 문제.
수정 을 더 했 지만 횟수 가 많 지 않 기 때문에 우 리 는
수 정 된 점 을 기록 한 후에 먼저 숫자 를 기록 한 다음 에 옮 겨 다 닌 다.
기 록 된 배열 은 수 정 된 수 를 더 해 야 하 는 지, 이전의 수 를 판단 한다.
지 울 지 말 지.
코드 는 다음 과 같 습 니 다:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
map<int,int > mp;
map<int,int >::iterator it;
vector<int >vc;
void fen(int x){
vc.clear();
for(int i=2;i*i<=x;i++){
if(x%i==0){
vc.push_back(i);
while(x%i==0) x/=i;
}
}
if(x>1) vc.push_back(x);
}
LL solve(int x,int p){
LL ans =(LL)x*(x+1)/2;
fen(p);
//cout<<"vc.size() "<<vc.size()<<endl;
for(int i=1;i<(1<<vc.size());i++){
int cnt = 0;
LL tmp = 1;
for(int j=0;j<vc.size();j++){
if((1<<j)&i) tmp*=vc[j],cnt++;
}
LL k = x/tmp;
k = (k+1)*k/2*tmp;
if(cnt%2) ans -= k;
else ans += k;
}
return ans;
}
int gcd(int a,int b){
return b ? gcd(b,a%b) : a;
}
int main()
{
int t,n,m,ord,x,y,p;
scanf("%d",&t);
while(t--){
mp.clear();
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d",&ord);
if(ord==2){
scanf("%d%d",&x,&y);
mp[x]=y;
}
else{
scanf("%d%d%d",&x,&y,&p);
LL ans = solve(y,p)-solve(x-1,p);
//printf("ans= %d
",ans);
for(it=mp.begin();it!=mp.end();it++){
if(it->first>=x&&it->first<=y){
if(gcd(it->first,p)==1) ans -= it->first;
if(gcd(it->second,p)==1) ans +=it->second;
}
}
printf("%I64d
",ans);
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.