头像

无忧无虑的蓝




离线:11小时前


最近来访(33)
用户头像
不动的大图书馆
用户头像
_Paradise_
用户头像
稚始稚终
用户头像
diandian1
用户头像
゚Presidentwolf
用户头像
sd6f5
用户头像
fxzcloud
用户头像
用户头像
夏悸
用户头像
硫化细菌
用户头像
lys111
用户头像
红红火火
用户头像
支支吾吾
用户头像
la_la_wanf
用户头像
未来i

活动打卡代码 AcWing 893. 集合-Nim游戏

include[HTML_REMOVED]

using namespace std;
const int N=110,M=1e4+10;
int n,m;
int f[M],s[N];
int sg(int x)
{
if(f[x]!=-1) return f[x];
set[HTML_REMOVED] S;
for(int i=0;i[HTML_REMOVED]=sum) S.insert(sg(x-sum));
}
for(int i=0;;i++)
if(!S.count(i))
return f[x]=i;
}
int main()
{
cin>>m;
for(int i=0;i[HTML_REMOVED]>s[i];
cin>>n;
memset(f,-1,sizeof(f));
int res=0;
for(int i=0;i[HTML_REMOVED]>x;
res^=sg(x);
}
if(res) printf(“Yes”);
else printf(“No”);
return 0;
}



活动打卡代码 AcWing 892. 台阶-Nim游戏

include[HTML_REMOVED]

using namespace std;
typedef long long ll;
int main()
{
int n;
cin>>n;
ll res=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(i%2!=0)
res^=x;
}
if(res!=0)
puts(“Yes”);
else
puts(“No”);
return 0;
}



活动打卡代码 AcWing 891. Nim游戏

include[HTML_REMOVED]

using namespace std;
typedef long long ll;
int main()
{
int n;
cin>>n;
ll res=0;
while(n–)
{
int x;
cin>>x;
res^=x;
}
if(res==0)
puts(“No”);
else
puts(“Yes”);
return 0;
}




欧拉函数 O(N)=1到N中所有与N互质的数的个数,如果可以把N写成它的分解质因数公式:

N=p1的a1次方 * p2的a2次方 * .....pk的ak次方

则它的欧拉函数等于N(1-1/p1)(1-1/p2)*…(1-1/pk),这是由容斥原理得到的(数学集合论),

我们将n减去所有它的因子的倍数,这其中有些数被减了两次,如p1,p2共同的倍数,我们再逐一加上每两个数的倍数,再减去每三个数的倍数…就能得到与N互质的数的个数了。
1 ~ N 中与 N 互质的数的个数被称为欧拉函数

欧拉函数的证明
利用容斥原理,求1 ~N-1中与N互斥的数的个数s
拆分出N的质因子p1、p2、p3…
s = N - N/p1 - N/p2 - N/p3-…-N/pk
+N/(p1p2) + N/(p1p2) + … + N/(p1pk) + … + N/(pk-1pk)
- N/(p1p2p3) - N/(p1p2p4) - … -N/(pk-2pk-1pk)
+N/(p1p2p3p4) + … + N/(pp-3pp-2pp-1pp)
…(以此类推)

p1的倍数由N/p1个,p2的倍数有N/p2个…pk的倍数有N/pk个,因此要减去。
但是有的数同时是p1和p2的倍数,所以会被重复减去,因此在第二行加回。
但是有的数同时是p1、p2、p3的倍数,在第一行会被重复减去三次,而在第二行会重复加回三次,相当于没变,因此要在第三行减去。
以此类推。。。。。。。
最后欧拉函数的公式如下:s = N * (1-1/p1) * (1-1/p2) * (1-1/p3) … * (1-1/pk)



活动打卡代码 AcWing 890. 能被整除的数

include[HTML_REMOVED]

using namespace std;
typedef long long ll;
const int N=20;
int p[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i[HTML_REMOVED]>p[i];
}
int res=0;
for(int i=1;i<1<[HTML_REMOVED]>j&1)
{
if((ll)tp[j]>n)
{
t=-1;
break;
}
s++;
t
=p[j];
}
}
if(t==-1)
continue;
if(s&1)
res+=n/t;
else
res-=n/t;
}
cout<<res<<endl;

}



活动打卡代码 AcWing 890. 能被整除的数

include [HTML_REMOVED]

using namespace std;
typedef long long ll;
const int N = 20;
int p[N], n, m;
int main()
{
cin>>n>>m;
for(int i=0;i[HTML_REMOVED]>p[i];
}
int res=0;
for(int i=1;i<1<[HTML_REMOVED]>j&1)
{
if((ll)tp[j]>n)
{
t=-1;
break;
}
s++;
t
= p[j];
}
}
if (t == -1)
continue;

    if (s & 1)
        res += n / t;  
    else
        res -= n / t;  
}   
cout << res << endl;
return 0;

}




include[HTML_REMOVED]

using namespace std;

const int N = 110;
int n;
int g[N][N];

int gauss()
{
int r=0,c;
for(int c=0;c<n;c) //按列进行枚举
{
int t = r; //找到非0行,用t进行存储
for(int i=r;i<n;i
)
if(g[i][c])
t=i;

    if(!g[t][c]) continue; //没有找到1,继续下一层循环

    for(int i=c;i<=n;i++) swap(g[r][i],g[t][i]);  //把第r行的数与第t行交换。

    for(int i=r+1;i<n;i++)    //用r行把下面所有行的当前列消成0
        if(g[i][c])
            for(int j=n;j>=c;j--)
                g[i][j] ^= g[r][j];
    r++;
}
if(r<n)
{
    for(int i=r;i<n;i++)
    {
        if(g[i][n]) return 2;
    }
    return 1;
}

for(int i=n-1;i>=0;i--)
{
    for(int j=i+1;j<n;j++)
    {
        g[i][n] ^= g[i][j ]* g[j][n];
    }
}
return 0;

}
int main()
{
cin>>n;
for(int i=0;i[HTML_REMOVED]>g[i][j];
}
}

int t = gauss();
if(t==0)
{
    for(int i=0;i<n;i++)
    {
        cout<<g[i][n]<<endl;
    }
}
else if(t==1) puts("Multiple sets of solutions");
else puts("No solution");
return 0;

}




include[HTML_REMOVED]

using namespace std;
typedef long long ll;
const int mod=1e9+7;
int eg(int a, int b)
{
int res=1;
while(b)
{
if(b&1)
res=(ll)resa%mod;
a=(ll)a
a%mod;
b>>=1;
}
return res;
}

int main()
{
int n;
cin>>n;
int res=1;
for(int i=2n;i>n;i–)
res=(ll)res
i%mod;
for(int i=n;i;i–)res=(ll)reseg(i,mod-2)%mod;
res=(ll)res
eg(n+1,mod-2)%mod;
cout<<res<<endl;
return 0;
}



活动打卡代码 AcWing 888. 求组合数 IV

include[HTML_REMOVED]

using namespace std;
const int N = 5010;
int primes[N], cnt;
int sum[N];
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i )
{
if (!st[i]) primes[cnt
] = i;
for (int j = 0; primes[j] <= n / i; j )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int get(int n, int p)
{
int res = 0;
while (n)
{
res += n / p;
n /= p;
}
return res;
}
vector[HTML_REMOVED] mul(vector[HTML_REMOVED] a, int b)
{
vector[HTML_REMOVED] c;
int t = 0;
for (int i = 0; i < a.size(); i
)
{
t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (t)
{
c.push_back(t % 10);
t /= 10;
}
return c;
}
int main()
{
int a, b;
cin >> a >> b;
get_primes(a);
for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];
sum[i] = get(a, p) - get(a - b, p) - get(b, p);
}
vector[HTML_REMOVED] res;
res.push_back(1);

for (int i = 0; i < cnt; i ++ )
    for (int j = 0; j < sum[i]; j ++ )
        res = mul(res, primes[i]);

for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
puts("");

return 0;

}



活动打卡代码 AcWing 887. 求组合数 III

include[HTML_REMOVED]

using namespace std;
typedef long long LL;
int qmi(int a,int k,int p)
{
int res = 1;
while(k)
{
if(k&1)res = (LL)resa%p;
a = (LL)a
a%p;
k>>=1;
}
return res;
}
int C(int a,int b,int p)
{
if(b>a)
return 0;
int res = 1;

for(int i=1,j=a;i<=b;i++,j--)
{
    res = (LL)res*j%p;
    res = (LL)res*qmi(i,p-2,p)%p;
}
return res;

}
int lucas(LL a,LL b,int p)
{
if(a<p && b<p)return C(a,b,p);
return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

int main()
{
int n;
cin >> n;
while(n–)
{
LL a,b;
int p;
cin >> a >> b >> p;
cout << lucas(a,b,p) << endl;
}
return 0;
}