hdu 4407 용척 원리
19494 단어 HDU
/*
* A/win.cpp
* Created on: 2012-9-8
* Author : ben
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
typedef long long LL;
const int MAXM = 1010;
const int MAXN = 400009;
const int PRIME_LEN = 168;
int primes[PRIME_LEN] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373,
379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457,
461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557,
563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827,
829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929,
937, 941, 947, 953, 967, 971, 977, 983, 991, 997 };
int primeFactor[MAXM], primeFactorLen;
typedef struct Change {
int x;
int y;
} Change;
Change changes[MAXM];
int CI;
int last[MAXN];
LL gcd(LL a, LL b) {
LL r;
while(b) {
r = a % b;
a = b, b = r;
}
return a;
}
LL getlcm(LL a, LL b) {
LL c = gcd(a, b);
return a / c * b;
}
bool isCoPrime(int a, int b) {
int r;
while (b) {
r = a % b;
a = b, b = r;
}
return a == 1;
}
void findPrimeFactor(int p) {
int temp = (int) sqrt(1.0 * p);
primeFactorLen = 0;
for (int i = 0; (i < PRIME_LEN) && (primes[i] <= temp); i++) {
if (p % primes[i] == 0) {
primeFactor[primeFactorLen++] = primes[i];
while (p % primes[i] == 0) {
p /= primes[i];
}
}
}
if (p > 1) {
primeFactor[primeFactorLen++] = p;
}
}
inline LL primeNSum(LL x, LL data) {
return data * ((x / data) * (x / data + 1) / 2);
}
void dfs(int now, int count, LL lcm, LL &ret, int x) {
lcm = getlcm(lcm, primeFactor[now]);
if (count % 2 == 0) {
ret += primeNSum(x, lcm);
} else {
ret -= primeNSum(x, lcm);
}
for (int i = now + 1; i < primeFactorLen; i++) {
dfs(i, count + 1, lcm, ret, x);
}
}
LL getsum(LL x) {
if(x <= 0) {
return 0;
}
LL ret = x * ( x + 1) / 2;
for (int i = 0; i < primeFactorLen; i++) {
dfs(i, 1, primeFactor[i], ret, x);
}
return ret;
}
void work(int x, int y, int p) {
findPrimeFactor(p);
LL sum = getsum(y) - getsum(x - 1);
for (int i = 0; i < CI; i++) {
if(last[changes[i].x] != i) {
continue;
}
if (changes[i].x >= x && changes[i].x <= y) {
int oldnum = changes[i].x;
int newnum = changes[i].y;
if (isCoPrime(oldnum, p)) {
sum -= oldnum;
}
if (isCoPrime(newnum, p)) {
sum += newnum;
}
}
}
printf("%I64d
", sum);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int T, N, M, op, x, y, p;
scanf("%d", &T);
while(T--) {
CI = 0;
scanf("%d%d", &N, &M);
for(int i = 0; i < M; i++) {
scanf("%d", &op);
if(op == 1) {
scanf("%d%d%d", &x, &y, &p);
work(x, y, p);
} else {
scanf("%d%d", &changes[CI].x, &changes[CI].y);
last[changes[CI].x] = CI;
CI++;
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu4671(다교리그 7--수 시뮬레이션)클릭하여 링크 열기 제목: n과 서버, m개의 데이터베이스가 있고 모든 데이터베이스는 서버를 연결해야 하지만 모든 데이터베이스는 서버를 연결하는 우선순위가 있습니다.모든 데이터베이스의 서버 우선순위를 구하다.또한 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.