Codeforces Round #489 (Div. 2)##
A. Nastya and an Array###
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define frep(i,a,b) for(int i=a;i>=b;--i)
#define mem(W) memset(W,0,sizeof(W))
#define pb push_back
typedef long long ll;
const int N = 100;
const int inf = 0x3f3f3f3f;
inline int read() {
char c=getchar(); int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
using namespace std;
int n,ans;
map<int,int> M;
int main() {
n = read();
rep(i,1,n){
int x=read();
if(x&&!M[x]){
M[x]=1;
++ans;
}
}
printf("%d
",ans);
return 0;
}
B. Nastya Studies Informatics###
(gcd(a,b) = x, lcm(a,b) = y) , 即 (gcd(frac {a}{x},frac {b}{x}) = 1, frac {a*b}{x} = frac{a}{x}*b = y)，那么我们可以直接枚举(frac{a}{x})来检查a，b是否在[l,r]内记入答案，只需要枚举(sqrt{y})以内的数即可。（卡的太久导致C没时间检查。。。直接凉了
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define frep(i,a,b) for(int i=a;i>=b;--i)
#define mem(W) memset(W,0,sizeof(W))
#define pb push_back
typedef long long ll;
const int N = 100;
const int inf = 0x3f3f3f3f;
inline ll read() {
char c=getchar(); ll x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
using namespace std;
ll x,y,l,r,ans,ans2;
set< pair<ll,ll> > s;
ll LCM(ll a,ll b){return a*b/__gcd(a,b);}
int main() {
l=read();r=read();x=read();y=read();
if(x==y){
if(l<=x&&x<=r)return puts("1"),0;
else return puts("0"),0;
}
if(y%x||y<x)return puts("0"),0;
if(y==1){
if(x==1&&l<=x&&x<=r)return puts("1"),0;
else return puts("0"),0;
}
for(ll i=1;i*i<=y;++i){
if(y%(x*i)==0&&__gcd(i*x,y/i)==x&&LCM(i*x,y/i)==y){
if(l<=i*x&&y/i<=r&&l<=y/i&&i*x<=r)s.insert(make_pair(i*x,y/i)),s.insert(make_pair(y/i,i*x));
}
}
printf("%d
",(int)s.size());
return 0;
}
C. Nastya and a Wardrobe###
稍微展开写一下，可以发现规律，然后公式就很显然了，具体见代码。注意特判。
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define frep(i,a,b) for(int i=a;i>=b;--i)
#define mem(W) memset(W,0,sizeof(W))
#define pb push_back
typedef long long ll;
const int N = 100;
const int inf = 0x3f3f3f3f;
inline int read() {
char c=getchar(); int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
using namespace std;
const int mod = 1e9 + 7;
ll q_pow(ll a,ll b) {
ll ans=1;
while(b){
if(b&1)ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
ll n,k;
int main() {
scanf("%I64d%I64d",&n,&k);
if(n==0)return puts("0"),0;
n%=mod;
printf("%I64d
",((q_pow(2,k+1)*n)%mod-(q_pow(2,k)-1)%mod+mod)%mod);
return 0;
}
D. Nastya and a Game###
(p = s*k ≤ 2*10^{18})，所以如果每次乘一个大于1的数，p最多需要(log{(2*10^{18})})个数相乘。那么只需要按题意枚举左端点，每次跳到下一个非1的位置，对于连续的一段1，计算最大，最小值就可以判断是否包含符合条件的位置。
#include <bits/stdc++.h>
typedef long long ll;
const int N = 2e5 + 100;
using namespace std;
int n,k;
ll a[N],sum[N];
int nxt[N];
void init() {
for(int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
nxt[n] = n+1;
for(int i=n-1;i>=1;--i) {
if(a[i+1] == 1) nxt[i] = nxt[i+1];
else nxt[i] = i+1;
}
}
int ck1(ll a, ll b) {return a*1.0 > LONG_MAX*1.0/b;}
int ck(ll x1, ll x2, ll p) {
if(p%k==0) {
p/=k;
if(x1<=p&&p<=x2) return 1;
}
return 0;
}
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) scanf("%I64d",&a[i]);
init();
int ans = 0;
for(int L=1;L<=n;++L) {
ll x=1;
for(int R=L;R<=n;R=nxt[R]) {
if(ck1(x, a[R])) break;
x*=a[R];
if(ck(sum[R]-sum[L-1], sum[nxt[R]-1]-sum[L-1], x)) ++ans;
}
}
printf("%d
", ans);
}
以后用markdown，然而代码高亮的问题还没解决，所以。。。
大概能看了。