HDU3234&&UVA12232&&LA4487:Exclusive-OR(经典带权并查集)永利网址:

HDU3234&&UVA12232&&LA4487:Exclusive-OR(经典带权并查集)

Problem Description You are not given n non-negative integers
X0, X1, …, Xn-1 less than
220 , but they do exist, and their values never change.

I’ll gradually provide you some facts about them, and ask you some
questions.

There are two kinds of facts, plus one kind of question:

永利网址 1

Input There will be at most 10 test cases. Each case begins with two
integers n and Q (1 <= n <= 20,000, 2 <= Q <=
40,000). Each of the following lines contains either a fact or a
question, formatted as stated above. The k parameter in the questions
will be a positive integer not greater than 15, and the v parameter in
the facts will be a non-negative integer less than 220. The
last case is followed by n=Q=0, which should not be processed.
Output For each test case, print the case number on its own line, then
the answers, one on each one. If you can’t deduce the answer for a
particular question, from the facts I provide you before that
question, print “I don’t know.”, without quotes. If the i-th fact
(don’t count questions) cannot be consistent with all the facts
before that, print “The first i facts are conflicting.”, then keep
silence for everything after that (including facts and questions). Print
a blank line after the output of each test case.

Sample Input

2 6
I 0 1 3
Q 1 0
Q 2 1 0
I 0 2
Q 1 1
Q 1 0
3 3
I 0 1 6
I 0 2 2
Q 2 1 2
2 4
I 0 1 7
Q 2 0 1
I 0 1 8
Q 2 0 1
0 0

Sample Output

Case 1:
I don't know.
3
1
2
Case 2:
4
Case 3:
7
The first 2 facts are conflicting.

Source 2009 Asia Wuhan Regional Contest Hosted by Wuhan University

题意:
对于n个数a[0]~a[n-1],但你不知道它们的值,通过逐步提供给你的信息,你的任务是根据这些信息回答问题
I P V :告诉你a[P] = V I P Q V:告诉你a[P] XOR a[Q] = V Q K
P1..PK:询问a[P1]^a[P2]^…a[PK]的值
思路: 很经典的并查集题目 r[a]记录的是a与其父亲节点的异或值
通过并查集合并的过程同时更新路径上的r值 令fa,fb分别是a,b,的父亲节点
我们知道r[a]永利网址, = a^fa,r[b]=b^fa,a^b=c
那么在合并fa,fb的时候,令fb为fa的父节点 那么就有r[fa]=fa^fb
而r[a]=a^fa,所以fa=a^r[a] 同理fb=b^r[b] 所以r[fa] =
r[a]^r[b]^a^b = r[a]^r[b]^c
当然对于一个节点合并问题不好解决,此时可以添加一一个新节点n作为根节点,使得n的值为0,那么任何值与0的异或都是本身
这样一来合并问题就解决了
然后对于查询而言,对于n是根节点的我们不需要考虑,但是对于不是以n为跟节点的,根节点的值被重复计算了,这个时候我们要统计根节点被统计的次数,如果是奇数次,那么必然是无法确定的了

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define lson 2*i
#define rson 2*i+1
#define LS l,mid,lson
#define RS mid+1,r,rson
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 20005
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define lowbit(x) (x&-x)
const int mod = 1e9+7;

int n,m,tot;
int father[N],r[N],num[N],u,v,w,vis[N];
char str[100];

int find(int x)
{
    if(x!=father[x])
    {
        int fx = father[x];
        father[x] = find(father[x]);
        r[x]^=r[fx];
    }
    return father[x];
}

bool Union(int a,int b,int c)
{
    int fa = find(a),fb=find(b);
    if(fa==fb)
    {
        if((r[a]^r[b])!=c) return false;
        return true;
    }
    if(fa==n) swap(fa,fb);
    father[fa] = fb;
    r[fa] = r[a]^r[b]^c;
    return true;
}

int query()
{
    int i,j,cnt,ans = 0;
    MEM(vis,0);
    for(i = 0; i

http://www.bkjia.com/cjjc/1018001.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1018001.htmlTechArticleHDU3234UVA12232LA4487:Exclusive-OR(经典带权并查集)
Problem Description You are not given n non-negative integers X 0 , X 1
, …, X n-1 less than 2 20 , but they do exist, a…

Mophues


Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 327670/327670 K
(Java/Others)
Total Submission(s): 1669    Accepted Submission(s): 675
 


Problem Description

As we know, any positive integer C ( C >= 2 ) can be written as the
multiply of some prime numbers:
    C = p1×p2× p3× … × pk
which p1, p2 … pk are all prime numbers.For example, if C = 24,
then:
    24 = 2 × 2 × 2 × 3
    here, p1 = p2 = p3 = 2, p4 = 3, k = 4

Given two integers P and C. if k<=P( k is the number of C’s prime
factors), we call C a lucky number of P.

Now, XXX needs to count the number of pairs (a, b), which 1<=a<=n
, 1<=b<=m, and gcd(a,b) is a lucky number of a given P ( “gcd”
means “greatest common divisor”).

Please note that we define 1 as lucky number of any non-negative
integers because 1 has no prime factor.

 

 


Input

The first line of input is an integer Q meaning that there are Q test
cases.
Then Q lines follow, each line is a test case and each test case
contains three non-negative numbers: n, m and P (n, m, P <=
5×105.
Q <=5000).

 

 


Output

For each test case, print the number of pairs (a, b), which
1<=a<=n , 1<=b<=m, and gcd(a,b) is a lucky number of
P.

 

 


Sample Input

2

10 10 0

10 10 1

 

 


Sample Output

63

93

 

 


Source


2013 ACM/ICPC Asia Regional Hangzhou
Online

 

 


Recommend

liuyiding   |   We have carefully selected several similar problems for
you:  6022 6021 6020 6019 6018 

 

//Source:http://acm.hdu.edu.cn/showproblem.php?pid=4746


Description(题意):

任何整数C ( C >= 2 )都可以写成素数之积
C = p1×p2× p3× … × pk
其中, p1, p2 … pk 是素数。如 C = 24, 则 24 = 2 × 2 × 2 × 3, 其中, p1 = p2 = p3 = 2, p4 = 3, k =

  1. 给定两整数 P和 C, 若 k<=P ( k是 C的素因子个数),称 C是P的幸运数.
    现小X需计算的点对 (a, b)的个数,其中1<=a<=n , 1<=b<=m,
    gcd(a,b)是 P的幸运数 ( “gcd”是最大公因数).
    注意:因为1无素因子,定义1为任何非负数的幸运数.

 

Input

    首行有一个整数 T,表示有 T 组测试数据.接下来有T行,每行是一种测试数据,含3个非负整数n, m 与P (n, m, P <= 5×105. T <=5000).

Output

    对每种测试数据,输出对 (a, b)的个数,其中 1<=a<=n , 1<=b<=m,
且 gcd(a,b) 是 P的幸运数.

Sample
Input

2

10 10 0

10 10 1

Sample
Output

63

93

永利网址 2

 

//num[j]记录j的因子数。
//g[j][num[i]]用于计算具有相同个数的素因子的i的?(j/i)之和,
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int M=5e5+5,N=19;
int n,m,p,T,g[M][N],num[M];
int tot,prime[M/3],mu[M];bool check[M];
int calc(int y,int x){
    int res=0;
    while(!(y%x)) y/=x,res++;
    return res;
}
void sieve(){
    n=5e5;mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!check[i]) prime[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*prime[j]<=n;j++){
            check[i*prime[j]]=1;
            if(!(i%prime[j])){mu[i*prime[j]]=0;break;}
            else mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=2;i<=n;i++) if(!num[i]) for(int j=i;j<=n;j+=i) num[j]+=calc(j,i);
    for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) g[j][num[i]]+=mu[j/i];
    for(int i=1;i<=n;i++) for(int j=1;j<19;j++) g[i][j]+=g[i][j-1];
    for(int i=1;i<=n;i++) for(int j=0;j<19;j++) g[i][j]+=g[i-1][j];
}
ll solve(int n,int m,int p){
    if(p>=19) return 1LL*n*m;
    if(n>m) swap(n,m);
    ll ans=0;
    for(int i=1,pos=0;i<=n;i=pos+1){
        pos=min(n/(n/i),m/(m/i));
        ans+=1LL*(n/i)*(m/i)*(g[pos][p]-g[i-1][p]);
    }
    return ans;
}
int main(){
    sieve();
    for(scanf("%d",&T);T--;){
        scanf("%d%d%d",&n,&m,&p),
        printf("%I64d\n",solve(n,m,p));
    }
    return 0;
}