异或约数和
ฅ'ω'ฅ♪

异或约数和

题目传送门[51nod1984]

题意

定义 f(i) 为 i 的所有约数的异或和,

给定 n(1≤n≤1014) ,

求 f(1) xor f(2) xor f(3) xor...xor f(n) (其中xor表示按位异或)

样例解释:

f(1) = 1 f(2) = 1 xor 2 = 3 f(3) = 1 xor 3 = 2 f(4) = 1 xor 2 xor 4 = 7 1 xor 3 xor 2 xor 7 = 7

思路

首先看到这种与异或累和有关的想起的应该是

0^0=0 1^0=1 1^1=0 A^0=A A^A=0

若记某个数为N,其约数集为{ n1 , n2 , n3……} 则只需要,对在全体约数集中出现次数为奇数的约数进行 ans^=ni , 最终的结果就是答案 ; 然后就可以得到……

明显地,这种方法时间复杂度为 O(n)。

优化

我们就可以考虑做一个分块; 定义左界Lef为约数n , 右界Rig为与n在全体集中出现次数相同的最大约数 。 就可以得到这么一个整除分块 ,我们只需要对出现次数为奇数的段进行约数和,每次都ans^=段和 ,便可以得到答案; 那么问题又来了 , 如何得到段和呢 。 如果定义G(x)为1~x的异或和,H(l,r)为l ~ r 的异或和 即在正整数上有H(l , r )=G( r )^G( l - 1 ) ; 而至于求G(x)则有O(1)的算法:

f(0, n)  =
n       n % 4 == 0
1       n % 4 == 1
n +1    n % 4 == 2
0       n % 4 == 3
inline int Sigxor( int n )
{   
    return ((n%4)&1) ? ((n%4)>>1)^1 : ((n%4)>>1)^n ;    
}

到这里我们的问题就全都解决啦 o ’ u ’ o !

标程

#include <bits/stdc++.h>
#define N 100050
#define lodou long double
#define lll __int128
#define INmF 0x3f3f3f3f
#define lbt(x) (x&amp;(-x))
#define mes(a,b) memset(a,b,sizeof(a))
#define qwq(a,b) for(int i=a ;i<=b;++i)
#define qeq(a,b) for(int j=a ;j<=b;++j)
#define qaq(a,b,c) for(ll i=a ; i<=b ;i=c+1)
#define IOS ios::sync_with_stdio(false)
#define  UPCASE( c ) ( ((c) >= 'c' &amp;&amp; (c) <= 'z') ? ((c) - 0x20) : (c) )
using namespace std;
const double Eps = 1e-8 ;
const double pi  = acos(-1) ;
const long long mod = 1e9+7 ;
typedef long long int ll;
inline ll pow_mod (ll a,ll b) {ll res=1;a%=mod; if(b<0) return -1; for(;b;b>>=1){if(b&amp;1)res=res*a%mod;a=a*a%mod;}return res;}
inline ll fas_mul (ll a,ll b) { return ( (a*b-(ll)(((long double)a*b+0.5)/mod)*mod)%mod+mod)%mod ; }

namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int __int128
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' &amp;&amp; c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar ( F[ -- cnt ] ) ;
    }
    #undef I_int

}using namespace io ;

inline ll Sigxor( ll n )
{   return ((n%4)&amp;1) ? ((n%4)>>1)^1 : ((n%4)>>1)^n ;    }

ll Blocking( ll n )
{
    ll  res=0 ,
        tem=0 ;
    qaq( 1 , n , tem ){
        tem=n/(n/i) ;//分块
        if( (n/i)&amp;1 )
            res^=Sigxor(i-1)^Sigxor(tem);//i~tem段的异或和
    }
    return res ;
}
unsigned main()
{
    ll n=read();
    outn(Blocking(n));
}
CANCEL

-评论-

Here you can post what you want to say, if you have more information please contact me by the following way.

-昵称-
-QQ-
-邮箱-
想说些什么?
-SUBMIT-

-电联 Phone-

+86 18520664652

-邮箱 Email-

boogieLing_o@163.com

boogieLing_o@qq.com

Your name. OS platform Browser model

What do you want to say?

created time

游說萬乘苦不早,著鞭跨馬涉遠道。

阿凌的貓爬架

幸會,

激活Ubuntu

转到“设置”以激活Ubuntu。

R0's board.