Codeforces Round #279 (Div. 2) C. Hacking Cypher

2284 단어 수학.codeforces
세 문 제 를 풀 지 못 했다.점수 가 떨어지다.구덩이 에 빠지다.
이 문 제 는 우선 스스로 한 번 냈 다.해 키 드 에 시간 이 초과 되 었 습 니 다.생각해 보니까자신 은 n ^ 2 의 복잡 도 입 니 다.시간 을 초과 하 는 것 도 필연 적 인 것 이다.
그리고 알고리즘 을 고 쳐 요. 혹은 복잡 도
바로 판단 하여 말 하기 쉽다.그냥 시 뮬 레이 션 하면 돼.그러나 문 제 는 후반 부 에 b 의 나머지 가 0 인지 아 닌 지 를 어떻게 판단 하 느 냐 하 는 것 이다.바로 자신의 문제 다.
사실 123 대 3 에 나머지 를 취한 다.정상 적 인 사 고 는 1 대 3 으로 남 으 면 안 되 고 12 대 3 으로 남 으 면 0 을 얻 을 수 있다. 3 이 더 되면 3 에 나머지 를 취한 다.이것 은 우리 가 아 는 과정 이다.
그래도 이렇게 3 대 3 으로 나머지 0 을 받 을 수 있어 요. 그리고 2 대 3 으로 나머지 2 를 얻 었 습 니 다.  그리고 12 대 3 으로 나머지 를 0 으로 받 는 것 도 괜 찮 습 니 다. 
원 리 는 바로 123% 3 = (100% 3 + 20% 3 + 3% 3)이번에 점수 떨 어 지면 떨 어 지 는 걸 로. 
지식 만 배우 면 돼. 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN 1000000+10
#define INF (1<<30)
#define mod 123456789
int aa[MAXN] = {0};
int bb[MAXN] = {0};
int main (){
    char s[MAXN];
    scanf("%s",s);
    int d = 0;
    int len = strlen(s);
    int a,b;
    scanf("%d%d",&a,&b);
    for(int i = 0; i < len; i++){
        d = d*10+s[i]-'0';
        d %= a;
        if(d == 0){
            aa[i] = 1;
        }
    }
    d = 0;
    LL t = 1;
    for(int i = len-1; i >= 0; i--){
        d = (d%b+(s[i] - '0')%b*t%b)%b;
        d %= b;
        t = t*10%b;
        if(d == 0){
            if(s[i] == '0')
                continue;
            else
                bb[i] = 1;
        }
    }
    int wh = -1;
    for(int i = 0; i < len; i++){
        if(aa[i] && bb[i+1]){
            wh = i;
            break;
        }
    }
    if(wh != -1){
        printf("YES
"); for(int i = 0; i <= wh; i++) printf("%c",s[i]); printf("
"); for(int i = wh+1; i < len; i++) printf("%c",s[i]); printf("
"); } else printf("NO
"); return 0; }

좋은 웹페이지 즐겨찾기