UVA 11361Investigating Div-Sum Property
제목: [a, b] 이 구간에 몇 개의 수 x가 만족하는지, x%k=0&x의 각 위치의 수와 y%k=0을 구하세요.
분석: 수학 기초 예제 5.
코드:
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=2000010;
const int MAX=151;
const int MOD1=1000007;
const int MOD2=100000009;
const double EPS=0.00000001;
typedef long long ll;
const ll MOD=1000000007;
const ll INF=10000000010;
typedef unsigned long long ull;
int k,q[12][90][90],dp[12][90][90],ten[12];
int get(int w,int u,int v) {
if (w==0&&u==0&&v==0) return 1;
if (w==0) return 0;
if (q[w][u][v]) return dp[w][u][v];
for (int i=0;i<10;i++)
dp[w][u][v]+=get(w-1,((u+i)%k+k)%k,((v+i*ten[w])%k+k)%k);
q[w][u][v]=1;
return dp[w][u][v];
}
int d[15];
int pd(int x) {
int y=x,sum=0;
while (x) { sum+=x%10;x/=10; }
if (sum%k==0&&y%k==0) return 1;
return 0;
}
int cala(int x) {
int i,j,u=0,v=0,g=0,ret=0;
if (pd(x)) ret++;
while (x) {
d[++g]=x%10;x/=10;
}
for (i=g;i>0;i--) {
for (j=0;j<d[i];j++)
ret+=get(i-1,((u+j)%k+k)%k,((v+j*ten[i])%k+k)%k);
u=((u+d[i])%k+k)%k;
v=((v+d[i]*ten[i])%k+k)%k;
}
return ret;
}
int main()
{
int a,b,t,i;
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &a, &b, &k);
if (k>=90) printf("0
");
else {
memset(q,0,sizeof(q));
memset(dp,0,sizeof(dp));
ten[1]=1;for (i=2;i<=10;i++) ten[i]=(ten[i-1]*10%k+k)%k;
printf("%d
", cala(b)-cala(a-1));
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.